[C++]백준 - 12852번 문제

12852번: 1로 만들기 2 (acmicpc.net)

12852번: 1로 만들기 2

 

12852번 : 1로 만들기 2

---

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

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

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

 

입력

---

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

 

 

출력

---

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

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

 

 

---

 

생각해 볼 점

---

DP의 역추적 문제입니다.

 

DP로 구한 최소 횟수 뿐만 아니라, 실제로 어떻게 1로 만들었는지의 과정을 출력해야 합니다.

 

DP 배열과, Trace라는 배열 2개를 준비하여 다음과 같이 저장합니다.

 

DP[i] = i값이 1이 되도록 연산한 최소 횟수

Trace[i] = i값이 1이 되도록 최소 횟수로 연산할 때, 연산 된 다음 숫자

 

예를 들어, i = 9일 경우에 두 번만에 1로 만들 수 있습니다.

 

이 경우, 다음과 같이 저장됩니다.

DP[1] = 0, DP[3] = 1, DP[9] = 2

Trace[1] = 0, Trace[3] = 1, Trace[9] = 3

 

이렇게 저장된 Trace를 순서에 따라 출력하면 정답을 구할 수 있습니다.

 

 

코드

---

#include <iostream>
using namespace std;

int *dp;
int *trace;
//재귀함수 - 다이나믹 프로그래밍
int solution(int X)
{
    if(X < 1) return 9999;
    if(X == 1) return 0;
    if(dp[X] != 0) return dp[X];
    
    //X-1의 경우
    int results[3];
    results[0] = solution(X - 1);
    
    int min_r = results[0];
    trace[X] = X - 1;
    
    //2로 나눈 경우
    if(X % 2 == 0)
    {
        results[1] = solution(X / 2);
        if(results[1] < min_r) 
        {
            trace[X] = X / 2;
            min_r = results[1];
        }
    }
    //3으로 나눈 경우
    if(X % 3 == 0)
    {
        results[2] = solution(X / 3);
        if(results[2] < min_r) 
        {
            trace[X] = X / 3;
            min_r = results[2];
        }
    }
    dp[X] = min_r + 1;	//세가지 경우 중 가장 작은 값 + 1
    
    return dp[X];
}

int main()
{
    int X;
    cin >> X;
    dp = new int[X + 1];	//DP
    trace = new int[X + 1];	//DP의 역추적용
    fill_n(dp, X + 1, 0);
    fill_n(trace, X + 1, 0);
    
    cout << solution(X) <<"\n";
    for(int i = X; 0 < i;)
    {
        cout << i << " ";
        i = trace[i];
    }
    delete[] trace;
    delete[] dp;
    return 0;
}

 

그 외

---