[DP] 1로 만들기

문제

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

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

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

 

예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.

1. 26 - 1 = 25
2. 25 / 5 = 5
3. 5 / 5 = 1

입력 조건

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

출력 조건

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

---

아이디어

원래의 나라면 문제를 봤을 때 그리디를 생각했을 것이고, 실제로도 그랬다. 하지만 이 문제는 잘 알려진 DP 문제이다. 함수가 도출되는 과정을 그림으로 그려보면 이해하는 데 도움이 된다.

 

예를 들어 X = 6 일 때, 함수는 아래와 같이 호출된다.

점화식으로 표현하면 아래와 같다. 점화식 끝에 1을 더해주는 이유는 함수의 호출 횟수를 구해야 하기 때문이다.

• a_i = min(a_i-1, a_i/2, a_i/3, a_i/5) + 1

코드

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int X = Integer.parseInt(br.readLine());
// dp 테이블
int[] dp = new int[30001];
// Bottom Up
for(int i=2; i<X+1; i++) {
    // 현재 수에서 1을 빼는 경우
    dp[i] = dp[i-1] + 1;
    // 현재 수가 2로 나누어 떨어지는 경우
    if(i % 2 == 0) {
        dp[i] = Math.min(dp[i], dp[i/2] + 1);
    }
    // 현재 수가 3으로 나누어 떨어지는 경우
    if(i % 3 == 0) {
        dp[i] = Math.min(dp[i], dp[i/3] + 1);
    }
    // 현재 수가 5로 나누어 떨어지는 경우
    if(i % 5 == 0) {
        dp[i] = Math.min(dp[i], dp[i/5] + 1);
    }
}
System.out.println(dp[X]);