[Python] 1로 만들기

백준 1463번

문제 설명

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

풀이

dp 문제이다.
사실 풀기는 진작 풀었는데 자꾸 틀렸다고 떠서 뭐가 문제인지 해설을 찾아보기까지 했는데, 어이없게도 단순 오타 때문이었다...
처음 보면 greedy 문제로 착각할 수도 있지만 그리디 문제는 나누기를 먼저 시행했을 때 항상 최솟값이 나와야 하지만 이 경우는 -1을 먼저 수행하는 게 빠른 경우가 있기 때문에 dp로 풀어야 한다. (ex) 10)

점화식은 다음과 같다.

dp[i] = min(dp[i - 1]+ 1, dp[i / 2]+ 1, dp[i / 3]+ 1)

i라는 수는 해당 연산을 수행하기 전(+1)이기 때문이다.

제출 코드

n = int(input())

dp = [0] * (n + 1)

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