[Python] 1로 만들기 - 백준 (DP)

해당 글은 백준 1463번 문제 '1로 만들기'를 다룬다.

문제

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

1463번: 1로 만들기

 

설명

3개의 연산을 섞어서 1로 만드는 최소의 경우의 수는 이전 결과를 통해서 구하면 되는 DP 문제이다.

-1은 무조건 연산이 가능하므로 dp[i] = dp[i-1]+1을 해주고,

2나 3으로 나누어 떨어지는 연산은 -1한 dp값과 나누기를 했을때의 dp값과 비교해서 최소값을 선택하면 된다.

여기서 2, 3으로 둘다 나누어 떨어지는 경우의 수가 있을 수도 있으므로 if-elif문이 아닌 if-if문으로 두 경우를 모두 계산해서 가장 최소값을 입력하게 해야한다. 

 

코드

n = int(input())
dp = [0]*(n+1)

for i in range(2, 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])