[C++ 백준 풀이] 12852번 : 1로 만들기 2 (DP, 다이나믹 프로그래밍 응용)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 난이도 Silver I에 해당하는 문제인 "12852번 : 1로 만들기 2"의 풀이 코드와 해설을 다루고 있습니다.

 

이 문제는 다이나믹 프로그래밍, DP를 응용하는 풀이를 포함하고 있으므로, 동적 프로그램이에 대한 배경 지식이 필요한 문제입니다.

 

 

12852번 : 1로 만들기 2

 

정수 N을 입력받았을 때 3으로 나누거나, 2로 나누거나 1을 빼는 3가지의 연산 중 일부를 적절히 조합해서 가장 적은 연산으로 1에 도달할 수 있는 루트를 출력하는 문제입니다.

탐색을 해야 하지만 연산의 종류의 수가 매 단계마다 3가지가 존재하므로 거듭제곱꼴의 형태로 매우 많아지기 때문에, 동적 프로그래밍을 반드시 활용해야하는 문제입니다.

다만 문제에서는 N을 작게 연산해나가기 때문에, 배열의 기록 순서를 어떻게 저장해 나갈 것인지에 대해 아이디어가 필요한 문제입니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래 접은 글에 정리되어 있으니 참고해주세요.

#include <iostream>
using namespace std;

int dp[1000005] = {0, };
int Min(int a, int b) { return a<b?a:b; }

int main() {
    int N;
    cin >> N;
    for(int i=1; i<=N; i++) dp[i] = i-1;
    for(int i=2; i<=N; i++) {
        dp[i] = Min(dp[i], dp[i-1]+1);
        if(i%2 == 0) dp[i] = Min(dp[i], dp[i/2]+1);
        if(i%3 == 0) dp[i] = Min(dp[i], dp[i/3]+1);
    }
    cout << dp[N] << "\n";
    while(1) {
        cout << N << " ";
        if(N == 1) return 0;
        if(N%2 == 0 && dp[N] == dp[N/2]+1) N /= 2;
        else if(N%3 == 0 && dp[N] == dp[N/3]+1) N /= 3;
        else N--;
    }
}

 

3가지의 연산에 대해 생각해보면 모두 정수 N이 작아지는 연산들뿐이므로, N보다 작은 정수들은 모두 N보다 연산이 많이 필요합니다.

따라서 수가 증가하거나 감소하는 어느 단방향을 잡고 dp 배열에 기록해 나가도 모든 값이 바르게 저장될 수 있습니다.

위의 풀이에서는 1부터 N까지 역으로 연산을 해나간 다음, 출력할 때 N에서부터 수를 줄여나가며 dp 배열의 값을 출력하는 방법을 선택했습니다.

dp[i]의 값은 dp[i-1], dp[i/2], dp[i/3] 중에서 가장 작은 값 + 1이 되므로 dp에 N까지의 배열 값을 저장해주고, 출력할 때 최단 루트대로 출력을 해주어야 하므로 dp[N]에서부터 가장 작은 dp값을 가진 배열 값을 출력해주면 됩니다.

 

 

위의 풀이 코드를 제출해보면 8ms라는 짧은 시간에 모든 테스트케이스를 통과함을 확인할 수 있습니다.