[Python] 백준(BOJ) 1463번: 1로 만들기 - dp

문제

1463번: 1로 만들기

풀이

다이나믹 프로그래밍으로 풀 수 있는 문제

배열을 하나 만들어서 N까지 채워주는 방식으로 풀었다.

1부터 3까지는 0, 1, 1으로 채워주고

그 뒤부터는 3으로 나눈 값(나누어 떨어지는 경우), 2로 나눈 값(나누어 떨어지는 경우), 1을 뺀 값 세가지 중 가장 작은 값에 1을 더해서 배열에 넣어줬다. 

import sys

N = int(sys.stdin.readline())

arr = [0, 0]

for i in range(2, N+1):

    if i <= 3:
        arr.append(1)
    else:
        li = []
        if i % 3 == 0:
            li.append(arr[int(i/3)] + 1)
        if i % 2 == 0:
            li.append(arr[int(i/2)] + 1)
        li.append(arr[i-1]+1)

        arr.append(min(li))

print(arr[N])