[백준 1740] 거듭제곱 (C++)

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

문제

---

3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다.

이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 수를 생각할 수 있다. 예를 들어 30은 27과 3의 합이므로, 이러한 수에 포함된다.

한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 N번째로 작은 수를 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 N이 주어진다. N은 500,000,000,000 이하의 자연수이다.

 

출력

---

첫째 줄에 한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 N번째로 작은 수를 출력한다.

 

문제 풀이

---

수학 문제.

 

십진수를 이진수로 변환하는 방법에서 착안하여 문제를 푼다. 2로 나누면서 그 나머지를 역순으로 나열하면 그것이 이진수가 된다. 마찬가지로 0이 아닐 때까지 2로 나누며 나머지가 1이라면 해당하는 자리의 수만큼 더해주면 된다.

예를 들어 6은 이진수로 110으로, 삼진수에서는 9의 자리와 3의 자리에 해당이 되며, 문제에서는 3의 2제곱과 3의 1제곱을 선택해 더한 것이 된다. 따라서 답이 12가 된다.

 

아래는 코드.

#include <iostream>
using namespace std;

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

	long long N;
	cin >> N;
	long long answer = 0;
	long long pow = 1;
	while (N != 0)
	{
		if (N % 2 == 1)
		{
			answer += pow;
		}
		pow *= 3;
		N /= 2;
	}
	cout << answer << "\n";
	return 0;
}