BOJ 4312 - 3의 제곱

문제

BOJ 4312 - 3의 제곱

양의 정수 n이 주어질 때, 서로 다른 3의 거듭제곱의 합으로 표현하라. 모든 양의 정수는 이렇게 표현 가능하다.

입력

여러 양의 정수가 주어지며, 0이면 종료한다.

출력

각 정수를 3의 거듭제곱 집합으로 표현하여 출력한다.

예제

풀이

n-1의 이진 표현에서 켜진 비트에 대응하는 3의 거듭제곱을 출력한다.

1. n에서 1을 빼서 0-인덱스로 변환한다
2. 이진 표현의 각 비트를 확인한다
3. i번째 비트가 1이면 3^i를 집합에 포함한다

핵심 아이디어: 3의 거듭제곱 부분집합과 양의 정수 사이의 일대일 대응은, n-1의 이진 표현이 어떤 거듭제곱을 포함할지를 결정하는 비트마스크가 된다.

코드

while True:
    n = int(input())
    if n == 0:
        break
    n -= 1
    print("{", end=" ")
    i = 0
    while n != 0:
        if n % 2:
            print(3**i, end=", " if n // 2 else " ")
        n //= 2
        i += 1
    print("}")

복잡도

• 시간: O(log N)
• 공간: O(log N)