백준 1740 거듭제곱

문제

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

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

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

입력

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

N이 5천 억이라 O(N)의 방법으로도 풀 수 없는 문제
굉장히 해맸던 문제이다

3^0 (1)

3^1, (10)
3^0 + 3^1 (11)

3^2,(100)
3^2 + 3^0, (101)
3^2 + 3^1 (110)
3^2 + 3^1 + 3^0 (111)

이런식으로 저장공간이 필요한 것을 알 수 있다 (규칙)
(서로 다른 3의 배수의 합으로 만들 수 있는 수들)

따라서 N번째 작은 수는 N을 2진수로 바꾼 값을 3진수로 계산하면 답이 나온다

따라서 O(logN)으로 계산 가능하며 5천억을 -> 38로 계산 가능

Python


def func() -> int:
    n = int(input())
    rst = ''
    # 3의 0 제곱  1 -> #1
    # 3의 1 제곱  3 -> #2
    # 3의 2 제곱  9 -> #3
    while n != 0:
        l = n % 2
        rst += str(l)
        n = n // 2
    st = rst[::-1]
    l = len(st) - 1
    rst = 0
    for i in range(len(st)):
        if st[i] == '1':
            rst += 3 ** l
        l -= 1
    
    return rst


if __name__ == '__main__':
    func()