파이썬에서 숫자가 서로 다른 3의 거듭제곱의 합인지 확인하는 프로그램

문제 개요

숫자 n이 하나 주어졌을 때, 이 숫자를 서로 다른(distinct) 3의 거듭제곱들의 합으로 나타낼 수 있는지 확인해야 합니다. 여기서 정수 y가 '3의 거듭제곱'이라는 것은 y = 3^x(x는 정수)를 만족하는 정수 x가 존재한다는 의미입니다.

예를 들어 입력이 n = 117이라면 결과는 True입니다. 117 = 3⁴ + 3³ + 3², 즉 81 + 27 + 9로 표현할 수 있기 때문입니다.

풀이 접근 방법

이 문제는 그리디(greedy) 기법으로 간단하게 해결할 수 있습니다. 가장 큰 거듭제곱부터 차례대로 확인하면서, 현재 값 n이 해당 거듭제곱보다 크거나 같으면 빼 주는 방식입니다. 모든 차감이 끝난 후 n이 정확히 0이 된다면 표현이 가능한 것이고, 0보다 큰 값이 남아 있다면 불가능합니다.

구체적인 절차는 다음과 같습니다.

i를 16부터 0까지 1씩 줄여 가며 반복합니다.
n이 3ⁱ보다 크거나 같으면 n에서 3ⁱ를 뺍니다.
반복 종료 후 n이 0보다 크면 False를 반환합니다.
그렇지 않으면 True를 반환합니다.

참고로 3¹⁶ = 43,046,721이므로, 일반적인 문제 제약 조건(예: n ≤ 10⁷)을 충분히 커버할 수 있는 범위입니다.

이 방법이 성립하는 이유는 3진법과 연관이 있습니다. 어떤 수가 서로 다른 3의 거듭제곱의 합으로 표현될 수 있다는 것은, 그 수를 3진법으로 나타냈을 때 각 자릿수가 0 또는 1뿐이라는 것과 동치입니다. 큰 자리부터 차감해 나가는 그리디 과정에서 마지막에 값이 남는다면, 어딘가에 같은 거듭제곱을 두 번 사용해야 하는 자리(즉, 3진법에서 2가 등장하는 자리)가 있다는 뜻입니다.

예제 구현

다음 파이썬 코드로 위 로직을 구현할 수 있습니다.

def solve(n):
   for i in range(16, -1, -1):
      if n >= pow(3, i):
         n -= pow(3, i)

   if n > 0:
      return False

   return True

n = 117
print(solve(n))

입력

출력

True

복잡도 분석

시간 복잡도는 최대 17번의 반복만 수행하므로 O(1)입니다. 공간 복잡도 역시 O(1)로, 추가 메모리가 필요하지 않습니다.