107. 1로 만들기

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

  a. X가 5로 나누어 떨어지면, 5로 나눈다.

  b. X가 3으로 나누어 떨어지면, 3으로 나눈다.

  c. X가 2로 나누어 떨어지면, 2로 나눈다.

  d. X에서 1을 뺀다.

• 정수 X가 주어졌으 ㄹ때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

예를 들어 정수가 26이면 다음과 같이 계산해서 2번의 연산이 최솟값이다.
1. 26 - 1 = 25 (d)
2. 25 / 5 = 5 (a)
3. 2 / 5 = 1 (a)

• 입력조건

  • 첫째 줄에 정수 X가 주어진다. (1 ≤ X ≤ 30,000)

• 출력조건

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

타뷸레이션(보텀업)을 이용한 풀이

x = int(input())

d = [0] * 30001

#예) x = 26

for i in range(2, x + 1):
  # d[26] = d[25] + 1
  #현재의 수에서 1을 빼는 경우
  d[i] = d[i - 1] + 1
  if i % 2 == 0:
    d[i] = min(d[i], d[i // 2] + 1)
  
  if i % 3 == 0:
    d[i] = min(d[i], d[i // 3] + 1) 

  if i % 5 == 0:
    d[i] = min(d[i], d[i // 5] + 1) 
    #d[25] = min(d[25], d[5] + 1)
    #d[5] = min(d[5], d[1] + 1)

print(d[x])

예를 들어 X = 6일 때, 함수가 호출되는 과정을 그리면 다음과 같을 것이다.

• f(2)와 같은 함수들이 동일하게 여러 번 호출되는 것을 알 수 있다. 이 문제에서 동일한 함수에서 구하는 값들은 동일해야 하므로 다이나믹 프로그래밍을 효과적으로 사용할 수 있다.

• 이제 문제에서 요구하는 내용을 점화식으로 표현해보자.
  aᵢ = min(aᵢ₋₁, aᵢ ⁄₂, aᵢ ⁄₃, aᵢ ⁄₅) + 1

  • 점화식 끝에 1을 더해주는 이유는 함수의 호출 횟수를 구해야 하기 때문이다.

• 위의 점화식의 토래도 보텀업 다이나믹 프로그래밍을 설계한다.

  • 실제 코드로 구현할 때는 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해서만 점화식을 적용할 수 있다.

  • 더해서 두 수 중에서 단순히 더 작은 수를 구하고자 할때는 파이썬에서의 min() 함수를 이용하면 간단하다.

C++ 코드

#include <bits/stdc++.h>

using namespace std;

// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 
int d[30001];
int x;

int main(void) {
    cin >> x;
    // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
    for (int i = 2; i <= x; i++) {
        // 현재의 수에서 1을 빼는 경우
        d[i] = d[i - 1] + 1;
        // 현재의 수가 2로 나누어 떨어지는 경우
        if (i % 2 == 0)
            d[i] = min(d[i], d[i / 2] + 1);
        // 현재의 수가 3으로 나누어 떨어지는 경우
        if (i % 3 == 0)
            d[i] = min(d[i], d[i / 3] + 1);
        // 현재의 수가 5로 나누어 떨어지는 경우
        if (i % 5 == 0)
            d[i] = min(d[i], d[i / 5] + 1);
    }
    cout << d[x] << '\n';
}