1463 - 1로 만들기

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

1463번: 1로 만들기

 

- Dynamic Programming

 

import sys
input = sys.stdin.readline

n = int(input())

dp = [0] * (n+4)
dp[2] = dp[3] = 1

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

print(dp[n])

감격스럽다

새로운 dp 유형이었는데 빠르게 풀어냈다 ㅎㅎ

 

if~elif~else 문으로 점화식을 만든건 좀 안 이쁘지만..

어쨌든 정답!!!!