[1463번] 1로 만들기

문제

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

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

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

 

문제접근법.

 

 예제에서 주어진 10을 보면, 10 -> 9 -> 3 -> 1이다. 9를 만들기 위해 연산의 사용하는 연산의 최솟값이 10에 사용될 것이라고 유추할 수 있다. 다이나믹 프로그래밍으로 문제를 접근해야 한다.

 

 1~10까지 직접 채워나가다 보면, 점화식을 찾을 수 있다.

1	2	3	4	5	6	7	8	9	10
0	1	1	2	3	2	3	3	2	3

 위에는 1~10까지의 숫자를 의미하고, 아래는 1을 만들기 위해서 필요한 최소 연산의 값을 의미한다. 직접 표를 채워나가면서 점화식을 발견할 수 있었다.

 

 연산의 최솟 값을 찾는 함수를 DP라고 지정하고,  i를 매개 변수로 넣어보겠다.

DP[i] = DP[i - 1] + 1

DP[i] = DP[i / 2] + 1(단, i % 2 == 0일 때)

DP[i] = DP[i / 3] + 1(단, i % 3 == 0일 때)

 

 위 3가지 식의 최솟값을 구하면 된다. 위의 해설과정이 잘 이해되지 않는다면, 다이나믹 프로그래밍 기초 문제를 먼저 풀어보면서 감을 잡거나, 위의 DP 표를 더 그려나가면서(~20) 채워보는 것을 추천한다.

 

해설코드(C++).

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int dp[1000001] = { 0 };
int N;
 
int main(void) {
    //freopen("input.txt", "r", stdin);
    cin >> N;
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;
 
    for (int i = 4; i <= N; i++) {
        int result = 1000000;
        for (int j = 1; j <= 3; j++) {
            int temp = 1000000;
            if (j == 1)
                temp = dp[i - 1];
            else if (j == 2 && i % 2 == 0)
                temp = dp[i / 2];
            else if (j == 3 && i % 3 == 0)
                temp = dp[i / 3];
            result = min(temp + 1, result);
        }
        dp[i] = result;
    }
 
    cout << dp[N] << endl;
    return 0;
}