백준 12851 숨바꼭질 2

앞서 풀었던 숨바꼭질 문제처럼 최소 비용을 구하면 된다.

 

최소 비용으로 가는 방법의 수는 다이나믹 프로그래밍 기법을 이용한다.

즉, 만약 처음 방문하는 거면 최소 비용으로 도달한 것이기 때문에 바로 앞의 위치까지 가는 방법의 수를 그대로 넣어준다.

이미 방문했던 곳에 최소 비용으로 다시 도달하게 되면, 방법이 더 있는 것이므로 바로 앞의 위치까지 가는 방법의 수와 이전에 현재 위치까지 오는 최소 비용 방법의 횟수를 더해준다.

 

코드는 아래와 같다.

#include <iostream>
#include <queue>
using namespace std;
 
int time[100001];
int cnt[100001];
 
int main(int argc, char** argv) {
    int n, k;
    cin >> n >> k;
 
    queue<int> q;
    q.push(n);
    time[n] = 1;
    cnt[n] = 1;
 
    while (!q.empty()) {
        int posi = q.front();
        q.pop();
 
        int prev = posi - 1;
        int next = posi + 1;
        int jump = posi * 2;
 
        if (prev >= 0) {
            //cnt에는 최소 비용으로 방문할 수 있는 방법만 저장한다.
            //만약 최소 비용으로 도달했다면 최소 비용으로 도달하는 방법이 더 있는 것이므로 더해준다.
            //다이나믹 프로그래밍 기법.
            if (time[posi] + 1 == time[prev])cnt[prev] += cnt[posi];
            if (time[prev] == 0) {
                q.push(prev);
                time[prev] = time[posi] + 1;
                //처음 방문하는 거면 최소 비용으로 방문하는 방법의 횟수가 posi까지 가는 방법의 횟수와 같다.
                cnt[prev] = cnt[posi];
            }
        }
        if (next < 100001) {
            if (time[posi] + 1 == time[next])cnt[next] += cnt[posi];
            if (time[next] == 0) {
                q.push(next);
                time[next] = time[posi] + 1;
                cnt[next] = cnt[posi];
            }
        }
        if (jump < 100001) {
            if (time[posi] + 1 == time[jump])cnt[jump] += cnt[posi];
            if (time[jump] == 0) {
                q.push(jump);
                time[jump] = time[posi] + 1;
                cnt[jump] = cnt[posi];
            }
        }
    }
 
    printf("%d\n%d\n", time[k] - 1, cnt[k]);
 
    return 0;
}