[백준/DP] - 1463 1로 만들기 (Python)

문제 링크

풀이과정

위 사진과 같이 1463은 작은 부분 문제의 최적해로 최적해가 이루어져 있고, 중복되는 계산이 등장하므로 DP를 이용해 문제를 풀어야한다.
정해진 연산(3으로 나누기, 2로 나누기, 1 빼기)을 통해 이전에 계산하여 최적해를 구한 예전 숫자가 나온다면 새 숫자에서 예전 숫자가 나올 때까지 연산한 횟수를 더하면 된다.

예를 들어, 6 같은 경우 3으로도 나누어 떨어지고 2로도 나누어 떨어진다. 먼저 6을 3으로 나누면 2가 되는데, 이 경우 2일 때 1이 되는 연산 횟수가 1이므로 6이 2가 되기 위해 수행한 연산의 횟수에 1을 더하면 된다(1+1=2). 같은 방식으로 6을 2로 나누면 3이 되는데, 이때 3에 저장된 값이 1이므로 이것도 똑같이 1+1=2가 된다. 마지막으로 6에서 1을 빼면 5가 되는데, 5에 저장된 값이 3이므로 1+3=4가 된다. 따라서 2, 2, 4 중 최솟값인 2가 6의 1이 되는 연산 횟수가 된다.

코드

a = int(input())

dp=[0,0,1,1,2]
for i in range(5, a+1):
    a3,a2,a1=10000,10000,dp[i-1] #min이니까 초기값 크게!!
    if i%3==0:
        a3=dp[i//3]
    if i%2==0:
        a2=dp[i//2]
    dp.append(1+min(a3, a2, a1))

print(dp[a])