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

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

 

 

이 문제는 N이 주어지고 

3가지 연산에 대해서 가장 최소 개수의 연산을 사용하여 1로 만드는 문제이다.

 

바로 드는 생각은 N을 노드로 생각하여 3가지 간선이 존재하여 bfs를 사용하여 풀 수 있겠다고 생각하였다. 근데 메모리적 측면으로 보았을때

큐 하나하나에 벡터로 역추적하면 메모리가 너무 커져서 다른 간단한 방법이 있을까 생각하여 dp를 생각하였다.

 

즉 모든 수에 대해서 최소연산의 개수로 사용하여 1로 만드는 테이블을 만들었다.

 

dp[i] = i값을 1로 만드는데 최소한의 연산 개수로 정의하였으며

 

dp[1] = 0으로 시작하여

 

점화식을 사용하여 dp 테이블을 구성하였다.

 

이후 dp[N] 부터 시작하여 3개의 값을 사용하여 값이 감소하는지 확인하였다 만약 감소하지 않은 경우 최적의 길이 아니며 이는 최소값이 될 수 없으므로 제외시켰다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct horse {
    int x;
    int y;
    int dir;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {0, 0, 0, 1, -1};
int dy[] = {0, 1, -1, 0, 0};
int N;
int dp[1000001];

void Print() {
    for(int i = 1; i <= N; i++) {
        cout << dp[i] << " ";
    }
}

void solve() {
    dp[1] = 0;

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

        if(i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);
    }

    int tmp = N;
    vector<int> v;
    v.push_back(tmp);

    cout << dp[N] << endl;

    while(tmp != 1) {
        if(tmp % 3 == 0 && dp[tmp / 3] < dp[tmp]) {
            v.push_back(tmp / 3);
            tmp /= 3;
            continue;
        }

        if(tmp % 2 == 0 && dp[tmp / 2] < dp[tmp]) {
            v.push_back(tmp / 2);
            tmp /= 2;
            continue;
        }

        v.push_back(tmp - 1);
        tmp--;
    }

    for(auto it : v) {
        cout << it << " ";
    }
}

void input() {
    cin >> N;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}