[C++] 12852 - 1로 만들기 2

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

12852번: 1로 만들기 2

 

 

 

BFS에서 각 조건문에 'N보다 작거나 같다'을 넣은 이유는

1로 만들기 위해 N에서 1을 빼거나 2를 나누거나 3을 나누는 연산을 하는건 N보다 커질 수 없다고 생각을 해서 넣었다.

 

#include<bits/stdc++.h>
 
#define endl '\n'
 
using namespace std;
 
typedef struct Data
{
    int value;
    int count;
}Data;
int dp[1000005][2];
 
void BFS(int N)
{
    Data p;
    queue<Data> Q;
    Q.push({1, 0});
 
    while(!Q.empty())
    {
        p = Q.front();
        Q.pop();
        if(p.value == N)
            return;
 
        if(p.value+1 <= N && dp[p.value+1][0] == 0)
        {
            dp[p.value+1][0] = p.value;
            dp[p.value+1][1] = p.count+1;
            Q.push({p.value+1, p.count+1});
        }
        if(p.value*2 <= N && dp[p.value*2][0] == 0)
        {
            dp[p.value*2][0] = p.value;
            dp[p.value*2][1] = p.count+1;
            Q.push({p.value*2, p.count+1});
        }
        if(p.value*3 <= N && dp[p.value*3][0] == 0)
        {
            dp[p.value*3][0] = p.value;
            dp[p.value*3][1] = p.count+1;
            Q.push({p.value*3, p.count+1});
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    dp[0][0] = 0;
    dp[1][0] = 0;
 
    int N, i;
    cin >> N;
 
    BFS(N);
    
    cout << dp[N][1] << endl;
    for(i = N; i != 0; i = dp[i][0])
        cout << i << ' ';
    // cout << 1;
    return 0;
}