문제
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번째로 작은 수를 출력한다.
예제 입력 1
4
예제 출력 1
9
나의 풀이
- 이 문제에서 주어지는 N은 억 단위를 넘어가기에 3의 거듭제곱 합을 일일이 구하면 시간초과가 발생할 것이다. 따라서 비트마스킹 알고리즘으로 필요한 지수만을 구한 뒤 최종 값을 연산해 출력하도록 구현했다.
- 서로 다른 3의 제곱수의 합으로 구성된 수는 1(3^0), 3(3^1), 4(3^0+3^1), 9(3^2), 10(3^0+3^2), 12(3^1+3^2), 13(3^0+3^1+3^2), 27(3^3), 28(3^0+3^3) ... 순으로 이어진다. 또한 이 수열의 순서를 이진수로 변환하면 1, 10, 11, 100, 101, 110, 111, 1000, 1001, ... 순으로 이어진다. 따라서 두 수열을 관찰하면 각 비트 위치 i를 3^i에 대응시킬 때 서로 다른 3의 제곱수의 합으로 나타낼 수 있음을 알 수 있다. 예제 1의 경우를 조금 더 살펴보면 N=4(:0b100)일 때 이진수 N의 2번째 자리에 1이 있으므로 답은 3^2이다. 따라서 이진수 N의 몇 번째 자리에 1이 포함되었는지만 파악하면 답을 쉽게 구할 수 있다.
import sys
answer,temp = 0, 1
N = bin(int(sys.stdin.readline()))[2:]
for n in reversed(N):
answer += (int(n)*temp)
temp *= 3
print(answer)
SAY CHEESE