17071 - 숨바꼭질 5
본문
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 $N$($0 \leq N \leq 500\,000$)에 있고, 동생은 점 $K$($0 \leq K \leq 500\,000$)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 $X$일 때 걷는다면 1초 후에 $X-1$ 또는 $X+1$로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 $2 \times X$의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 $1$을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 $K$, 1초가 지난 후 위치는 $K+1$, 2초가 지난 후 위치는 $K+1+2$, 3초가 지난 후의 위치는 $K+1+2+3$이다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 $0$보다 작은 좌표로, $50\text{만}$보다 큰 좌표로 이동하는 것은 불가능하다.
입력
첫 번째 줄에 수빈이가 있는 위치 $N$과 동생이 있는 위치 $K$가 주어진다. $N$과 $K$는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 $500\,000$을 넘는 경우에는 -1을 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 0.25sec | 512MB |
풀이
다른 숨바꼭질 문제들과 유사하다. 당연히 푸는 방식도 유사하다. 대부분의 문제에서 BFS를 통해 수빈이가 갈 수 있는 위치를 모두 찾아두는 방법을 사용했다. 그러므로 이 문제에서도 수빈이가 어떤 칸을 언제 도착할 수 있는가?를 찾는 과정을 중점적으로 생각해야한다.
문제에서 주어지는 조건부터 확인하자.
- 수빈이가 이동할 수 있는 방향
- $x = x -1$ // 1초
- $x = x + 1$ // 1초
- $x = 2 \times x$ // 1초
- 동생의 위치
- $k = k + \sum_{n=0}^{i} n $ // i초 이후
동생의 위치는 시간에 따라 특정 위치에 고정된다. 그러므로 우리가 찾아야하는 것은 ‘특정 시간에 특정 위치에 있을 동생을 수빈이가 따라잡을 수 있는가?’ 라는 질문의 답이다. 수빈이가 갈 수 있는 위치와 그 때의 시간을 같이 기록해야할 것이다.
그러면 BFS를 진행하자. 시간을 기록해야하므로 bool 형식의 visit 배열을 사용하지 말고, 최단시간으로 도착할 수 있는 시간을 기록한 int 형식의 배열을 visit 배열로 활용할 수 있을 것이다. 만약 3초 뒤에 동생이 특정 칸 $A$에 도달했는데, visit 배열에 적힌 값이 4초라면 동생은 이미 그 칸을 지나친 이후일 것이다. 그렇다면 수빈이는 다른 칸에서 동생을 따라잡아야할 것이다.
다만 동생이 수빈이보다 특정 칸 $A$에 늦게 도착한 경우 수빈이는 가만히 있는다면 동생을 잡을 수 있다. 다만 수빈이의 행동에는 ‘가만히 있는다’는 선택지가 없다. 가만히 있기 위해서는 다른 칸에 1번 갔다오는 방법이 있다. 갔다온다는 행동은 2초를 소요하므로, 그 사이에 동생이 도착한다면 동생을 따라잡을 수는 없다. 즉, 어떤 특정 칸에 $B$초에 도달했다면, $B+2$, $B+4$초 등에는 제자리에 있을 수 있지만, $B+1$, $B+3$초 등에는 제자리에 있을 수 없으므로, 동생이 이 때 도착했다면 이 칸에서는 동생을 잡을 수 없게 된다. 그래서, 수빈이가 특정 칸에 도착하는 시간을 최단시간으로만 기록하면 안되고, 최단시간을 홀짝으로 기록해둘 필요성이 있다. 특정 칸에 도달하면 제자리를 유지하는 것은 2초가 추가로 소요되므로 1개만 기록하면 되지 않냐고 생각할 수 있지만, 홀짝이 둘 다 가능한 경우가 있기 때문이다. (ex. 0초에 도달 후 x2배 하는 것으로 제자리를 유지할 경우, 이후 모든 칸들은 홀짝이 뒤바뀐 채 도달할 수 있음)
동생이 가는 경로를 target 배열로 기록하자. target 배열은 동생이 도달하는 칸과, 그 때의 시간을 기록한다. 이후 수빈이의 가능한 경로는 BFS 탐색을 통해 기록한다. 홀짝으로 최단시간을 기록하기 위해 dp 배열을 사용했다. visit 개념도 포함하는 역할을 수행한다. 만약 dp 배열에 기록된 값이 target에 기록된 값보다 작으면서 홀짝을 만족하고, 그 시간이 최소일 때 답으로 선택하게 된다.
- 참고 알고리즘 : BFS 탐색
코드
사용 언어 : C
최종 수정일 : 2024 / 3 / 12
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
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
typedef struct QueueNode {
int x;
int cnt;
} QN;
#define INF 987654321
#define MAX_IDX (500000 + 1)
int n, k;
int target[2][MAX_IDX];
int dp[2][MAX_IDX];
QN q[MAX_IDX * 6 + 1];
int f, r;
int result = INF;
#define min(a, b) (((a) > (b)) ? (b) : (a))
void init() {
for (int i = 0; i < MAX_IDX; ++i) {
for (int j = 0; j < 2; ++j) {
dp[j][i] = INF;
target[j][i] = INF;
}
}
return;
}
bool canBeReach(int a, int b) { return ((target[a][b] < INF) && (target[a][b] >= dp[a][b]) && ((target[a][b] - dp[a][b]) % 2 == 0)); }
int main() {
init();
scanf("%d %d", &n, &k);
int temp = k;
for (int i = 0; temp + i < MAX_IDX; ++i) {
target[i % 2][temp = (temp + i)] = i;
}
q[r++] = (QN){n, 0};
while (f < r) {
QN node = q[f++];
if (dp[node.cnt % 2][node.x] < INF) {
continue;
}
dp[node.cnt % 2][node.x] = node.cnt;
int x = node.x, cnt = node.cnt;
if (canBeReach(cnt % 2, x) == true) {
result = min(result, target[cnt % 2][x]);
continue;
}
if (x > 1) {
q[r++] = (QN){x - 1, cnt + 1};
}
if (x < MAX_IDX - 1) {
q[r++] = (QN){x + 1, cnt + 1};
}
if (x * 2 < MAX_IDX) {
q[r++] = (QN){x * 2, cnt + 1};
}
}
printf("%d", ((result == INF) ? -1 : result));
return 0;
}