다이나믹 프로그래밍 - 1로 만들기

< 문제제목 > 

[문제]

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

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

• 정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들려고 한다.
• 연산을 사용하는 횟수의 최솟값을 출력하시오.
• 예를 들어, 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.
  • 26 - 1 = 25
  • 25 / 5 = 5
  • 5 / 5 = 1

[입력]

• 첫째 줄에 정수 X이 주어진다. (1<=X<=30,000)

[출력]

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

예제 입력	예제 출력
26	3

---

아이디어

dp에 담을 정보는 i번째까지 왔을 때의 연산 최소 횟수이다. 그렇다면 dp에는 무얼 저장해야 할까? i // 2번째, i // 3번째, i // 5번째, i - 1번째 중 작은 수 + 1의 수를 저장해야 한다.

풀이 및 코드

n = int(input())
dp = [0] * (n + 1)
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1
    if (i % 2 == 0):
        dp[i] = min(dp[i // 2] + 1, dp[i])
    if (i % 3 == 0):
        dp[i] = min(dp[i // 3] + 1, dp[i])
    if (i % 5 == 0):
        dp[i] = min(dp[i // 5] + 1, dp[i])
print(dp[n])

후기

처음에 어떤 수를 저장해야 할지를 구상하지 않아서 조금 헤맸다. 다시 한번 점화식의 중요성을 느낄 수 있었던 문제이다.