1463번: 1로 만들기

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

 

아이디어

 

최솟값을 구해야 하므로 10^6 + 1개짜리의 배열 dp를 10^6+1 값으로 지정

 

이후 4부터 N까지 순회하며 dp에 최소 횟수를 저장한다.

만약 3으로 나누어 떨어진다면 dp[i // 3] + 1 값 따로 저장

만약 2로 나누어 떨어진다면 dp[i // 2] + 1 값 따로 저장

이후 dp[i -1] + 1값과 각각 저장한 모든 값의 최솟값을 구한다.

 

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

N = int(input())

crit = 1000001

dp = [crit] * (crit)
dp[1] = 0
dp[2] = 1
dp[3] = 1
for i in range(4, N + 1) :
    save_3 = crit
    save_2 = crit
    if i % 3 == 0 :
        save_3 = dp[i // 3] + 1
    if i % 2 == 0 :
        save_2 = dp[i // 2] + 1
    dp[i] = min(dp[i - 1] + 1, save_2, save_3)

print(dp[N])

 

- 헤맸던 점

if i % 3 == 0 :

   ...

elif i % 2 == 0 :

   ...

 

으로 해서 2로 나누어 떨어질 때의 최솟값을 반영하지 못했었다.