[백준/1463/파이썬] 1로 만들기 - DP

 

---

소스코드

x = int(input())

dp = [0]*(x+1)

dp[1] = 0

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

---

알고리즘

DP문제는 많이 풀어봐서 이번 문제는 그리 어렵지는 않았다.

1이 되기 위해서 필요한 연산의 숫자를 구하는 것 이다.

1. 2,3은 1에 2배,3배를 하면 된다.
2. 4는 2까지 걸린 연산 횟수의 1번 더(2배) 하면 된다. 
3. 5는 4까지의 연산에 1번더(+1) 
4. 6은 2까지의 연산에 1번더(*2)

최소 횟수에 대해 전에 걸 불러와서 연산해 나가는 방식이다.