[c++] 백준 12852 - 1로 만들기 2(dp)

0. [c++] 백준

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

1. 풀이

2. 소스코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int N;
 
void solve() {
    vector<vector<int> > V(N + 1, vector<int>(0,0));
    
    
    for (int i = 1; i < N; i++) {
        if (V[i + 1].empty() || V[i + 1].size() - 1 > V[i].size()) {
            V[i + 1] = V[i];
            V[i + 1].push_back(i);
        }
        if (i * 2 > N)
            continue;
        if (V[i * 2].empty() || V[i*2].size() - 1 > V[i].size()) {
            V[i * 2] = V[i];
            V[i * 2].push_back(i);
        }
        if (i * 3 > N)
            continue;
        if (V[i * 3].empty() || V[i * 3].size() - 1 > V[i].size()) {
            V[i * 3] = V[i];
            V[i * 3].push_back(i);
        }
    }
    cout << V[N].size() << endl;
    reverse(V[N].begin(), V[N].end());
    cout << N << " ";
    for (int i = 0; i < V[N].size(); i++) {
        cout << V[N][i] << " ";
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
    solve();
}

- 큐 활용

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int N;
 
void solve() {
    vector<vector<int> > V(N + 1, vector<int>(0,0));
    
    queue<int> qu;
    qu.push(1);
    while (!qu.empty()){
        int i = qu.front();
        qu.pop();
        if (!V[N].empty())
            break;
        if (V[i + 1].empty()) {
            V[i + 1] = V[i];
            V[i + 1].push_back(i);
            qu.push(i + 1);
        }
        if (i * 2 > N)
            continue;
        if (V[i * 2].empty()) {
            V[i * 2] = V[i];
            V[i * 2].push_back(i);
            qu.push(i * 2);
        }
        if (i * 3 > N)
            continue;
        if (V[i * 3].empty()) {
            V[i * 3] = V[i];
            V[i * 3].push_back(i);
            qu.push(i * 3);
        }
 
    }
    cout << V[N].size() << endl;
    reverse(V[N].begin(), V[N].end());
    cout << N << " ";
    for (int i = 0; i < V[N].size(); i++) {
        cout << V[N][i] << " ";
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
    solve();
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!