파이썬) 백준 알고리즘 | 1463번 : 1로 만들기

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

1463번: 1로 만들기

백준 1463 '1로 만들기' 문제입니다.

제가 처음 푸는 DP 문제인데 DP를 이해하지 못하다가 이 문제에서 처음으로 이해한 것 같습니다.

n마다 3으로 나누기, 2로 나누기, 1빼기 각각의 케이스를 시도하고 가장 작은 값을 취해주는 식으로 구현하였습니다.

import sys
input = sys.stdin.readline
n = int(input())
dp = [-1] * (n+1)
minValue = 99999999
for i in range(1, n+1):
    if i % 3 == 0:
        a = dp[i//3] + 1
    else:
        a = 999999
    if i % 2 == 0:
        b = dp[i//2] + 1
    else:
        b = 999999
    c = dp[i-1] + 1
    dp[i] = min(a, b, c)
print(dp[n])