(백준) 1463호: 1로 만들기 – (Python/Python)

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지가 있습니다.

1. X가 3으로 나누어지면 3으로 나눕니다.
2. X가 2로 나누어지면 2로 나눕니다.
3. 빼기 1.

정수 N이 주어지면 위의 세 가지 연산을 적절하게 사용하여 1로 만들려고 합니다. 연산이 사용된 최소 횟수를 출력합니다.

입력

첫 번째 줄에는 1보다 크거나 같고 106보다 작거나 같은 정수 N이 포함됩니다.

인쇄

첫 번째 줄에는 작업 수의 최소값이 출력됩니다.

암호

import sys
input=sys.stdin.readline

dp=(0)*((10**6)+1)

n=int(input())
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))

문제 해결

이것이 DP의 기본 문제이며, 최소값을 지속적으로 업데이트하여 문제를 해결하는 기본 방법입니다.