[백준 1463] 1로 만들기 - Python(파이썬)

초기 답안(BFS)

import sys


def solution(N):
    ans = 0
    while N:
        temp = []
        for n in N:
            if n == 1:
                return ans

            if not n % 3:
                temp.append(n // 3)
            if not n % 2:
                temp.append(n // 2)
            if n - 1 > 0:
                temp.append(n - 1)

        ans += 1
        N = temp


N = int(sys.stdin.readline().strip())
arr = [N]
print(solution(arr))

 

최적화 답안

import sys


def solution(N):
    if N in answer:
        return answer[N]

    answer[N] = 1 + min(solution(N // 3) + N % 3, solution(N // 2) + N % 2)

    return answer[N]


N = int(sys.stdin.readline().strip())
answer = {1: 0, 2: 1}
print(solution(N))