1463 1로 만들기

문제

코드

import sys

n = int(sys.stdin.readline())
# data[i] = 가는데 필요한 최소 수
data = [100000 for i in range(n+1)]
data[1] = 0
for i in range(2, n+1):
    if(i%2 == 0 and i%3 == 0):
        data[i] = min(data[i-1],data[i//2],data[i//3])
    elif(i%2 == 0):
        data[i] = min(data[i-1],data[i//2])
    elif(i%3 == 0):
        data[i] = min(data[i-1], data[i // 3])
    else:
        data[i] = data[i-1]
    data[i] += 1

print(data[n])

풀이

다이나믹 프로그래밍으로 풀었다.
즉 N까지 for문을 반복하면서 최솟값을 찾았는데
이전에 찾은 최솟값을 재사용했다는 의미이다.