[백준/BOJ] 17020 삼삼한 수 (파이썬 Python)

 

https://www.acmicpc.net/problem/17252

 

처음엔 경우의 수로 일일이 풀어야 하나 싶었는데,

 

3의 거듭제곱이 겹치지 않아야 한다는 조건에서 힌트를 얻었다.

 

즉, 현재 값에 최대한 근접한 3의 거듭제곱을 찾아 빼고 난 뒤의 값이 

 

여전히 위에서 찾은 3의 거듭제곱보다 크다면 한번 더 사용해야 하므로 이러한 조건에선 무조건 NO를 말하게 했다. 

 

이외 조건에선 마지막에 3^0을 포함해 현재 값에 계속해서 빼나갔을 때 0이되면

 

3의 거듭제곱으로 중복되지 않고 만들 수 있다는 얘기이므로 YES를 출력하게 했다. 

 

import sys
input = sys.stdin.readline

n = int(input())

def check(n):
    for i in range(21):
        tmp = pow(3,i)
        if tmp > n:
            return tmp // 3

while True:
    tmp = check(n)
    n -= tmp
    if n >= tmp:
        print('NO')
        break
    if n == 0:
        print('YES')
        break