[BOJ] 1740 거듭제곱

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

 

 

문제 풀이:

 

3의 제곱 -> 1 3 9 27 ....

 

3의 제곱으로 만들 수 있는 값들: 1 3 4 9 10 12 13....

 

1 -> 1

3 -> 3

4 -> 1+3

9 -> 9

10 -> 1+9

12 -> 3+9

13 -> 1+3+9

.

.

.

 

1은 3의 제곱 중 가장 작은 값이므로 [1]이라고 하자.

3은 [2]

9는 [3]

이라고 했을 때,

1 = [1]

3 = [2]

4 = [1]+[2]

9 = [3]

10 = [1]+[3]

12 = [2]+[3]

13 = [1]+[2]+[3]

 

이런식으로 바꿔서 생각할 수 있다. 

 

이를 이진수로 나타내보자.

1 = [1] = 1

3 = [2] = 10

4 = [1]+[2] = 11

9 = [3] = 100

10 = [1]+[3] = 101

12 = [2]+[3] = 110

13 = [1]+[2]+[3] = 111

 

다음과 같이 이진수로 나타낼 수 있다. 

 

즉, N을 이진수로 바꾼 후, 이를 3진수로 읽어내면 된다.

 

 

소스 코드:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
using namespace std;


long long n,res;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	long long three = 1, tmp = n;
	while (tmp > 0) {
		if (tmp % 2 == 1) res += three;
		tmp /= 2;
		three *= 3;
	}
	cout << res << '\n';
	return 0;
}