[1740] 거듭 제곱

https://www.acmicpc.net/problem/1740

와 너무 신기한 문제에요..ㅠㅠ

N이 진짜 말도안되게 커서 어떻게 접근해야할지 감도 안왔습니다..

규칙이 있나 찾아봤는데 규칙이 있는 것도 아니였습니다.

자료를 찾다보니... 3의 제곱수를 하나씩만 사용할 수 있는게 힌트였습니다!

진짜 엄청난 힌트더군요..

자꾸 사람들이 2진수 이야기를 하길래 무슨 소린가...했는데..

3의 제곱수를 하나씩만 사용한다는 얘기는 !!!

27 9 3 1 이렇게 있다고 치면!

                

27	9	3	1
0	0	0	1
0	0	1	0
0	0	1	1
0	1	0	0
0	1	0	1
0	1	1	0
0	1	1	1
1	0	0	0
1	0	0	1

어디서 많이 보던!!!!!! 표입니다!

그렇습니다! 하나만 쓰게되면 이진수처럼 됩니당!

그래서 N을 2진수로 바꾼 후에 이 2진수를 3진수를 이용해서 10진수로 바꾸면! 결과가 나옵니다.

예제에 N = 4였습니다.

4는 2진수로

100 입니다! 3진수로 100은 9입니다.

그래서 답은 9죠!

진짜 재밌는 문제입니다..... 소오름~~~

아래는 코드입니다.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
 
#define ll long long
using namespace std;
 
int main() {
    ll n;
    scanf("%lld", &n);
    
    queue<bool> q;
    while (n) {
        q.push(n % 2);
        n /= 2;
    }
 
    ll ans = 0;
    ll add = 1;
 
    while (!q.empty()) {
        ans += q.front() * add;
        add *= 3;
        q.pop();
    }
 
    printf("%lld", ans);
    
    return 0;
}