3의 거듭제곱 합
면접 대비시간 제한2초메모리 제한128 MB
N이 주어질 때, 서로 다른 3의 거듭제곱들의 합으로 나타낼 수 있는 양의 정수 중 N번째로 작은 수를 구하는 문제입니다.
문제
3의 거듭제곱은 3^0, 3^1, 3^2, ...처럼 이어지며, 값은 차례대로 1, 3, 9, 27, ...이다.
서로 다른 3의 거듭제곱을 하나 이상 골라 더하면 여러 자연수를 만들 수 있다. 예를 들어 30은 27 + 3으로 만들 수 있으므로 이런 수에 포함된다.
이렇게 만들 수 있는 수들을 작은 것부터 정렬했을 때, N번째 수를 구하시오.
입력
첫째 줄에 자연수 N이 주어진다.
N은 500,000,000,000 이하이다.
출력
서로 다른 3의 거듭제곱을 하나 이상 더해 만들 수 있는 수 중에서 N번째로 작은 수를 출력한다.