백준 1463번 파이썬 | 1로 만들기 (DP)

문제

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

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

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

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

풀이

1로 만들기는 대표적인 DP가 쓰이는 문제이다. 그리디의 1로 만들기도 있지만 이 문제의 경우 무조건 나눈다고 최적의 해를 얻는게 아니다.

따라서 매 경우 min을 따로 구해서 계산하면 된다. 

점화식은 2 이상일때 d[i]=d[i-1 or i//2 or i//3] +1 이다. i//2와 i//3은 2와 3으로 나누어 떨어질 때만 계산해주면 된다.

# 1463 1로 만들기
# DP

import sys
input = sys.stdin.readline

N = int(input())
d = [0] * 1000001
# d[1]=0 , d[2]= 1 , d[i]=d[i-1]+1
for i in range(2, N + 1):
    d[i] = d[i - 1] + 1

    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
print(d[N])