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

[문제]

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

12852번: 1로 만들기 2

[문제 풀이]

DP를 사용해서 푸는 문제이다.

1~1,000,000까지 DP배열에 해당 숫자를 입력하고( 1에서 순서대로 증가하면 그 숫자만큼의 결과가 나올테니까) for문으로 n까지 돌려보면서 만약 3이나 2로 나눠진다면 나눠진 dp 배열의 숫자에 1을 더하고 이와 같은 방법으로 인해서 도중에 이전 숫자에 1만 더하는 값이 더 커질수 있기 때문에 반복문 처음에 dp[i] = dp[i - 1] + 1;을 선언해줬다.

 

n부터 여태까지 왔던걸 확인하는 것은 반대로 반복문을 통해서 n에서 3이 나눠지고 해당 숫자가 dp[n / 3] == dp[n] - 1이라면 해당 위치를 출력 아니면 n / 2를 확인 그것도 아니면 현재 숫자 - 1의 dp 배열 위치를 출력해줬다.

[회고]

1. 처음에는 재귀로 풀었는데 범위가 1,000,000이라서 시간초과가 날 수밖에 없었다. 테스트를 돌려보니 시간초과 같앴는데 혹시 몰라 제출했더니 역시나 틀렸다.

2. 오랜만에 1차원 dp를 푸니까 생각보다 신경써야 할 부분이 많았다. 앞으로도 까먹지 않게 자주 돌아보자.

[코드]

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int dp[1000001];
int answer;
int n;

void solve(){

    dp[1] = 1;

    for(int i = 2;i<=n;i++){
        dp[i] = i;
    }

    for(int i = 2;i<=n;i++){
        dp[i] = dp[i - 1] + 1;
        if(i % 3 == 0){
            dp[i] = min(dp[i],dp[i / 3] + 1);
        }
        if(i % 2== 0){
            dp[i] = min(dp[i],dp[i / 2] + 1);
        }
    }

    cout<<dp[n] - 1<<endl;

    int count = n;

    cout<<n<<" ";
    
    while(count > 1){
        if(count % 3 == 0 && dp[count / 3] == dp[count] - 1){
            cout<<count / 3<<" ";
            count /= 3;
        }
        else if(count % 2 == 0 && dp[count / 2] == dp[count] - 1){
            cout<<count / 2<<" ";
            count /= 2;
        }
        else {
            cout<<count - 1<<" ";
            count -= 1;
        }
    }
    return;
}

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

    return 0;
}