[백준/DP] 1463 1로 만들기 (Python, 파이썬)

 

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

1463번: 1로 만들기

 

 

이 문제는 큰 문제를 작은 문제를 통해 풀 수 있으므로 DP를 이용해 풀 수 있다.

 

예를 들어보면,

4가 입력 되었을 때 4 -> 2 -> 1  이므로 정답은 2가 된다.

이번에는 12가 입력된다면 12/3 = 4이므로 4를 입력으로 했을 때의 정답에서 1을 더하면 된다.

 

이와 같이 이 문제는 작은 문제들을 통해 큰 문제를 해결 할 수 있다.

또한 큰 문제를 작은 문제로 쪼갤 수 있다.

 

D[N] = N을 1로 만드는 최소 연산 횟수

 

n = int(input())

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

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1 # 횟수 추가

    if i%2 == 0 and dp[i] > dp[i//2] + 1:
        dp[i] = dp[i//2] + 1

    if i%3 ==0 and dp[i] > dp[i//3] + 1:
        dp[i] = dp[i//3] + 1

print(dp[n])