Boj 12852 c++ 1로 만들기 2

https://www.acmicpc.net/problem/12852

 

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

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

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

 

1로 만들기 #1463 을 이미 풀었기에 횟수를 구하는 방법에는 큰 문제가 없었다. 우선 1을 뺀 값을 기본값으로 설정해놓은 후, 

2 또는 3으로 나누어 떨어지는 경우에는 더 유리한 것으로 업데이트하는 방식이다. 하지만 최적해에 도달하기까지의 경로를 출력하는 방법은 익숙하지가 않아 이번 기회에 새로이 공부하게 되었다.

 

우선 문제 자체는 bottom-up dp로 풀이하였다.

 

dp에서 최종 해까지의 경로를 추적하는 방법은 'Parent' 와 같이 dp배열과 같은 크기의 배열을 이용하는 것이다.

각각의 인덱스는 이전 숫자를 가리킨다.

ex) 10 -> 9 -> 3 -> 1이라면

Parent[10] = 9       ->       Parent[9] = 3     ->     Parent[3] = 1 과 같은 방식이다.

 

while문을 통해 인덱스 값을 하나씩 출력하고, 부모가 0이되는 순간(1로 만들어진 순간) 에 종료하면 된다.

 

전체코드

#include<iostream>
#define Max 1000001
using namespace std;

int dp[Max];
int Parent[Max];

int main(){
    int n;
    cin >> n;

    dp[1] = 0;
    Parent[1] = 0;

    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + 1;
        Parent[i] = i-1;


        if(i % 2 == 0 && dp[i] > dp[i/2]+1){
            dp[i] = dp[i/2] + 1;
            Parent[i] = i/2;
        }


        if(i % 3 == 0 && dp[i] > dp[i/3]+1){
            dp[i] = dp[i/3] + 1;
            Parent[i] = i/3;
        }

    }
    cout << dp[n] << "\n";
    cout << n << " ";
    while(Parent[n] != 0){
        cout << Parent[n] << " ";
        n = Parent[n];
    }
}