[C++] 백준 13549번: 숨바꼭질3

🔗 문제

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

 

 

✏️ 풀이

 

[알고리즘]

다익스트라

 

X*2로 이동할 경우는 가중치가 0이기 때문에 나이브하게 BFS로 풀면 안 된다.

이 경우는 다익스트라로 접근하여 최소 가중치를 찾아주는 방식을 떠올려서 풀면 된다.

 

 

[시간 최적화 방법]

• 수빈이가 동생보다 앞에 있다면 뒤로 한 칸씩 이동해줄 수밖에 없다.
• 수빈이가 동생과 같은 위치라면 연산이 필요 없다.

if(N >= K)
	  cout << N-K;
else
	  cout << getAnswer();

 

💾  소스

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
typedef pair<int, int> pii;

const int MAX_N = 200000 + 1;
int N, K;

int getAnswer()
{
    priority_queue<pii, vector<pii>, greater<>> pq;
    pq.push({0, N});

    vector<int> dp(MAX_N, 1e9);
    dp[N] = 0;

    while(!pq.empty())
    {
        int time = pq.top().first;
        int pos = pq.top().second;
        pq.pop();

        if(time > dp[pos]) continue;

        if(pos-1 >= 0 && dp[pos-1] > time+ 1)
        {
            dp[pos-1] = time+1;
            pq.push({dp[pos-1], pos-1});
        }

        if(pos+1 < MAX_N && dp[pos+1] > time + 1)
        {
            dp[pos+1] = time + 1;
            pq.push({dp[pos+1], pos+1});
        }
        
		// 가중치가 0인 곳 x*2
        if(pos*2 < MAX_N && dp[pos*2] > time)
        {
            dp[pos*2] = dp[pos];
            pq.push({dp[pos*2], pos*2});
        }
    }
    
    return dp[K];
}

int main()
{
    std::cin >> N >> K;
    int answer = 0;
    if(N >= K)
        cout << N-K;
    else
        cout << getAnswer();
    
    return 0;
}