[백준 12852번] 1로 만들기 2 (C++)

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

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N;
int dp[1000001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;

    for(int i=1; i<=N; i++) dp[i]=i-1;

    for(int i=2; i<=N; i++)
    {
        if(i%2==0) dp[i] = min(dp[i], dp[i/2]); //2번 조건
        if(i%3==0) dp[i] = min(dp[i], dp[i/3]); //1번 조건
        dp[i] = min(dp[i], dp[i-1]) + 1; //3번 조건, 1,2번 조건 비교
    }
    
    cout << dp[N] << "\n";

    while(N!=1) //역추적
    {
        cout << N << " ";
        if(dp[N] == dp[N-1]+1) N-=1;
        else 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;
    }
    cout << N;

    return 0;
}

 

기본적인 초기화는 3번 조건에 해당하는 값으로 설정해준다.

이에 따라 각 idx에 해당 하는 값은 idx-1의 횟수를 필요로 하므로 이에 맞게 초기화를 진행했다.

 

이후 1, 2번 조건에 대해 체크하며 더 작은 경우를 확인해준다.

또 이어서 기존 3번 조건과 1, 2번 조건을 통해 확인한 값을 비교해주며 최종적으로 제일 작은 값을 선택하고 횟수를 더해준다.

이렇게 구한 최종 dp[N]에 해당하는 값이 N에 대한 횟수이다.

 

이후 N을 기준으로 역추적을 통해 사용된 N을 출력한다.

기존 dp 식을 이용하여 1, 2, 3번 조건 중 어떤 조건을 통하여 현재 N에 도달했는지를 현재 dp 값과 직전 dp 값을 비교하여 어떤 조건과 같은 값을 갖는지 체크한다.

이후 해당 맞는 조건에 따라 N의 값을 감소시킨다. (-1, or /2 or /3)

N이 1이 될 때까지 반복하며, 반복문 종료후 마지막 N(1)을 출력해준다.