백준 12852번 - 1로 만들기 2

백준 12852번 - 1로 만들기 2

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

12852번: 1로 만들기 2

이 문제는 BFS, 다이나믹 프로그래밍 문제이다.

처음에는 top-down 방식으로 문제를 해결하려 했다.

문제의 조건에 맞게 코드를 짜 보았는데 마지막 출력에서 살짝 맘에 안 들었다.

출력 부분을 보면 n부터 내림차순으로 출력하는데, top-down 방식으로 해결하려면

dp[x]에는 x*3 또는 x*2 또는 x+1 이 들어가 있기 때문에 한번 vector나 배열에 다 넣고 오름차순 정렬을 해줘야 한다.

코드는 몇 줄 차이 안 나겠지만 시간 복잡도 면에서 botton-up 방식이 훨씬 좋을 것 같아서 다시 풀어보았다.

 

즉 다이나믹 프로그래밍을 사용하여 dp[x*3, x*2, x+1]에 x를 저장해 준다. (x는 1부터 시작)

이렇게 되면 x==n일 때 연산 횟수는 최솟값일 것이고 조건의 n제한이 10^6(1000000)이므로 시간 복잡도도 충분하다.

 

주의할 점은 무조건 dp[x*3, x*2, x+1]에 x를 저장하면 런타임 에러가 난다.

x*3, x*2, x+1이 10^6 보다 커질 수 있으므로 이에 대한 조건을 넣어 주어야 한다. 

 

#include <iostream>
#include <queue>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
 
int n;
int dp[1000001];
int dis[1000001];
bool check[1000001];
 
void bfs() {
    int x = 1;
    queue<int>q;
    q.push(x);
    check[x] = true;
    dp[x] = x;
    dis[x] = 0;
    int dx[3];
    while (1) {
        x = q.front();
        if (x == n)break;
        q.pop();
        dx[0] = x * 3;
        dx[1] = x * 2;
        dx[2] = x + 1;
        for (int k = 0; k < 3; k++) {
            int nx = dx[k];
            if (nx > 1000000) continue;
            if (check[nx] == false) {
                check[nx] = true;
                dp[nx] = x;
                dis[nx] = dis[x] + 1;
                q.push(nx);
            }
        }
    }
}
 
int main() {
    scanf("%d", &n);
    bfs();
    printf("%d\n", dis[n]);
    printf("%d ", n);
    while (n != 1) {
        printf("%d ", dp[n]);
        n = dp[n];
    }
}

그래프 이론(BFS)과 다이나믹 프로그래밍을 잘 이해하고 있다면 어렵지 않게 풀 수 있다.