[백준] 1463번 - 1로 만들기 (파이썬 코드) (feat. DP)

1. 문제

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

 

2. 코드

n = int(input())
dp = [0 for i in range(n+1)]

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1
    
    if i%3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)
    if i%2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
        
print(dp[n])

 

3. 알고리즘

점화식 : dp[N] = min(dp[N-1], dp[N//2] , dp[N//3]) + 1

 

1) 1을 빼준 경우를 우선 저장해놓는다.

2) 3으로 나뉠 경우, 1을 빼준 경우와 비교해서 최솟값을 저장한다.

3) 2로 나뉠 경우, 1을 빼준 경우(만약 2)에서 3으로 나뉜 경우로 바뀌었다면, 3으로 나뉜 경우)와 비교해서 최솟값을 저장한다.

(dp 문제는 점화식을 찾는게 포인트이다,,,, 나의 첫 dp 문제,,, 아주 많이 헤맸다,,,)