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

분류: DP, BFS /

 

문제

문제 링크

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 10⁶보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

 

풀이

- DP

#include <iostream>
using namespace std;

int dist[1000001];
int pre[1000001] {0, 1};

void move(int from, int to) {
    dist[to] = dist[from] + 1;
    pre[to] = from;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    for(int x=2; x<=N; x++) {
        move(x-1, x);
        if(x % 3 == 0 and dist[x/3] + 1 < dist[x]) move(x/3, x);
        if((x & 1) == 0 and dist[x >> 1] + 1 < dist[x]) move(x >> 1, x);
    }
    cout << dist[N] << '\n';
    for(int x=N; (cout << x << ' ', x != pre[x]); x = pre[x]);
}

# 1 -> N 역순 경로

거꾸로 1에서 N으로 가는 경로를 계산해도 같은 결과를 얻을 수 있다.

굳이 N에서 1로 문제가 나왔는데 1에서 N으로 가려는 이유는 N에서 1로 가는 경로로 출력해야하기 때문이다.

`s -> a -> b -> e` 경로의 경우 `e`가 어디에서 왔는지(`b`), `b`가 어디에서 왔는지(`a`), ... 를 기록하는 것이 쉽다.

즉 경로는 역순(`s <- a <- b <- e`)으로 기록하는 것이 간단하다. 

이렇게 역순으로 기록된 경로는 역순으로 그 경로를 온전히 알 수 있다.(`e -> b -> a -> s`)

 

문제에 나온데로 `N -> 1`의 경로를 계산하며 기록하면 역순(`1 -> N`) 이 기록되고 이를 따라 출력하면 `1 -> N`순서로 출력된다. 

`N -> 1` 순서로 출력하기 위해 `1 -> N`의 경로를 계산하고 기록한다.

 

# DP

이 문제는 DP로 해결 가능하다.

DP 문제는 부분 문제의 해를 이용해 전체 문제를 해결하는 점화식을 찾으면 된다.

이 문제의 경우 `dist[x] = min(dist[x/3], dist[x/2], dist[x-1]) + 1`이 이 점화식에 해당한다.

`dist[x]`의 의미는 1에서 `x`까지 가기 위한 최소 연산 숫자이다.

 

1 계단에서 N 계단까지 `+1` 계단, `x2` 계단, `x3` 계단 씩 오르는 최소 스텝을 구하는 문제와 같다. 

 

# 같이 보면 좋은 문제

[백준 - 1463] 1로 만들기

[백준 - 2579] 계단 오르기

[백준 - 16953] A -> B

[백준 - 1697] 숨바꼭질

[백준 - 13549] 숨바꼭질 3

[백준 - 13913] 숨바꼭질 4

[백준 - 17071] 숨바꼭질 5

 

- BFS

#include <iostream>
#include <queue>
using namespace std;

int dist[1000001];
int pre[1000001];
queue<pair<int,int>> Q;

void enqueue(int x, int nx, int nd) {
    if(dist[nx] and dist[nx] <= nd) return;
    Q.push({nx, nd});
    dist[nx] = nd;
    pre[nx] = x;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    Q.push({N, 0});
    pre[N] = N;
    while(not Q.empty()) {
        const auto [x, d] = Q.front(); Q.pop();
        int nd = d + 1;
        if(x % 3 == 0) enqueue(x, x / 3, nd);
        if((x & 1) == 0) enqueue(x, x / 2, nd);
        if(x > 1) enqueue(x, x -1, nd);
    }
    cout << dist[1] << '\n';
    int path[dist[1]+1];
    path[0] = N;
    for(int x=1, i=dist[1]; pre[x] != x; x = pre[x]) path[i--] = x;
    for(int x:path) cout << x << ' ';
}