백준 [1463] "1로 만들기"

동적계획법에 대한 개념이 부족
동적 계획법이란 과거 계산한 기록이 있을 시 이를 활용해 효과적으로 계산하는 방법

import sys
input = sys.stdin.readline
n = int(input())

dp = [0] * (n+1)

#n = 2 까지는 횟수가 0으로 동일
for i in range(2,n+1):
	# 2, 3으로도 나누어지지 않는 값은 -1 연산을 통해 그전 결과 참조
    dp[i] = dp[i-1] + 1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)

print(dp[n])

dp[i]에 대한 연산 방식은 모두 동일하기에 %2, %3을 진행했을 때 과거 계산한 기록을 통한 문제

dp[10] = min(dp[10], dp[10//2]+1)

10은 2로 나눠지기에 과거 dp[5]의 계산 결과를 사용하여 문제를 해결