백준 12852 - 1로 만들기 2(C++)

문제 링크입니다. https://www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

그래프와 DP가 합쳐진 문제였습니다.

1로 만드는 연산의 최소 횟수 및 과정을 출력하는 문제입니다.

연산의 최소 횟수를 구하는 방법은 간단합니다.

1부터 시작해 N까지 값을 증가하면서 저장해주면 됩니다.

1. 1을 뺏을 때

2. 3을 나눴을 때

3. 2로 나눴을 때

3가지 방법으로 나오는 값을 전부 비교해 가장 작은 값을 가져오면 됩니다.

 

이때 연산 과정은 하나의 과정을 추가해주면 되는데, 배열에 자신이 어떠한 값에서 도출되었는지를 저장해주면 됩니다.

예를 들어, 10의 최소값이 9에서 1을 더한 경우일 때,  connect[10] = 9로 저장해주는 것입니다.

for문이 모두 끝나, 최소 값이 구해졌을 때, X에서 시작해 배열의 값을 꺼내온다면, 연산 과정을 가져올 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int dp[1000001];
int connect[1000001];

void dfs(int x){
    cout << x << " ";
    if(x == 1) return;
    dfs(connect[x]);
}

void solve(){
    dp[1] = 1;
    for(int i = 2; i <= N; i++){
        if(dp[i-1] > 0) {
            dp[i] = dp[i-1] + 1;
            connect[i] = i-1;
        }
        if(dp[i/2] > 0 && i % 2 == 0){
            if(dp[i] > 0) {
                if(dp[i] > dp[i/2] + 1){
                   dp[i] = dp[i/2] + 1;
                   connect[i] = i/2;
                }
            }
            else {
                dp[i] = dp[i/2] + 1;
                connect[i] = i/2;
            }
        }
        if(dp[i/3] > 0 && i % 3 == 0){
            if(dp[i] > 0) {
                if(dp[i] > dp[i/3] + 1){
                    dp[i] = dp[i/3] + 1;
                    connect[i] = i/3;
                }
            }
            else {
                dp[i] = dp[i/3] +1;
                connect[i] = i/3;
            }
        }
    }
    cout << dp[N] - 1 << "\n"; 
    dfs(N);
}

int main(){
    cin >> N;
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요