아이디어
- 0-1 BFS 사용해서 동생위치 찾음
- 처음 좌표 넣을떄 2의배수 모두 추가
- 중간에 x2배(시간이 0) 다른것보다 먼저 수행해줘야함
- priority_queue 사용해서 수행
시간복잡도 계산
- 우선순위 큐 사용 : O(NlgN) = 1e5 * 20
- BFS : O(V+E)
- 노드 개수 : N
- 간선 개수 : 최대 N
- O(N)
- 총합 : O(NlgN + N) : O(NlgN) > 가능
인트 계산
- 가장 빠른시간 최대 1e5 > INT 가능
코드
|
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
58
59
60
61
62
|
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> pi2;
bool chk[100010];
int main() {
int N,K; cin >> N >> K;
priority_queue<pi2, vector<pi2>, greater<pi2>> pq;
// 시작값 큐에 넣어줌, 앞에는 시간, 뒤에는 노드
pq.push(make_pair(0,N));
fill(chk, chk+100010, 0);
chk[N] = 1;
if(N==K) {
cout << 0 << '\n';
return 0;
}
while(!pq.empty()) {
int et = pq.top().first;
int en = pq.top().second;
pq.pop();
if(en == K) {
cout << et << '\n';
return 0;
}
// 2배 먼저 해주기
int en2 = en * 2;
while(en2 <= 100000) {
if(chk[en2]) break;
chk[en2] = 1;
pq.push(make_pair(et, en2));
en2 = en2 * 2;
}
// 1더한것
if(en+1 <= 100000) {
if(chk[en+1] == false) {
chk[en+1] = 1;
pq.push(make_pair(et+1, en+1));
}
}
// 1뺀것
if(en-1 >= 0) {
if(chk[en-1] == false) {
chk[en-1] = 1;
pq.push(make_pair(et+1, en-1));
}
}
}
return 0;
}
|
cs |
문제유형
- BFS - 0/1 : 다른 노드보다 우선 수행해줘야하는 조건이 있을때 사용
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 6549 히스토그램에서 가장 큰 직사각형 쉬운 풀이 (C++/CPP) (0) | 2021.03.04 |
|---|---|
| 백준 1865 웜홀 쉬운 풀이 (C++/CPP) (0) | 2021.03.04 |
| 백준 9205 맥주 마시면서 걸어가기 (0) | 2021.03.03 |
| 백준 2887 행성 터널 쉬운 풀이 (C++/CPP) (0) | 2021.03.03 |
| 백준 10942 팰린드롬? 쉬운 풀이 (C++/CPP) (0) | 2021.03.03 |