1463번 - 1로 만들기

문제

1463번: 1로 만들기 (acmicpc.net)

1463번: 1로 만들기

풀이

예를 들어 X가 6인 경우, dp[6] = min(dp[5],dp[3],dp[2]) + 1이 될 것이다. 즉 X가 2로 나눠지는 경우와 3으로 나눠지는 경우에 대해서 점화식을 세우면 된다.

N = int(input())

dp = [0]*(10**6+1)
dp[1],dp[2],dp[3] = 0,1,1
for i in range(4,N+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])