반응형
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
알고리즘 종류
- 다익스트라
사고 과정
- 3가지 방법으로 이동하고 비용이 있다.
* x +1, time + 1
* x - 1, time + 1
* x * 2, time
- 이동하는 간선에 비용이 있고, 최소 비용으로 도착하는 방법을 찾기 위해서는 다익스트라 알고리즘을 사용한다.
구현(C++)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <iostream>
#include <queue>
#define MAX 100001
using namespace std;
int n, k;
int INF = 987654321;
int cost[MAX];
int answer = 0;
priority_queue<pair<int, int> > pq;
bool isValid(int x){
return x >= 0 && x < MAX;
}
void check(int next, int next_sec){
if( isValid(next) && cost[next] > next_sec){
cost[next] = next_sec;
pq.push({-next_sec, next});
}
}
void solution(){
for(int i=0; i<MAX; i++) cost[i] = INF;
pq.push({0, n});
cost[n] = 0;
while(!pq.empty()){
int here = pq.top().second;
int sec = -pq.top().first;
pq.pop();
// 뒤로 1칸, 앞으로 1칸, 2배 멀리 이동
check(here-1, sec+1);
check(here+1, sec+1);
check(here*2, sec);
}
cout << cost[k] << endl;
}
int main(void){
cin >> n >> k;
solution();
}
|
cs |
시행착오
- 우선순위 큐에서 pair<int, int>에 넣어주는 값을 잘 못 설정해서 고생했다. 최소 힙을 만들기 위해서 pair의 앞에 비용을 넣어주어야 했는데, 노드를 넣어서 최소 힙이 아니게 되었다. 그래서 시간초과가 났다. 다음부터는 heap에 비용과 노드를 넣을 때에 first에 비용을, second에 노드를 넣는 것을 잊어버리지 말자.
반응형