https://www.acmicpc.net/problem/2065
2065번: 나룻배
문제 강을 사이에 두고 위치한 두 정박장 사이를 한 대의 나룻배가 오가고 있다. 두 정박장은 강을 기준으로 왼쪽(left), 오른쪽(right)으로 구분한다. 제일 처음에는 나룻배가 왼쪽 정박장에 위치해 있다. 이 나룻배는 한번에 최대 M(1≤M≤10,000)명의 사람을 태울 수 있으며, 한 쪽 정박장에서 다른 쪽 정박장으로 이동하는데 양쪽 방향 모두 t(1≤t≤10,000)만큼의 시간이 걸린다. 나룻배는 손님을 한 쪽 정박장에서 다른 쪽 정박장으로 실어
www.acmicpc.net
|
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
76
77
78
79
80
81
82
83
|
#include<stdio.h>
#include<iostream>
#include<string>
#include<queue>
#define NSIZE 10000
using namespace std;
int M, t, N;
struct Data {
int time; string pos; int idx;
};
queue<Data>L;
queue<Data>R;
char pos = 'L';
int finalTime[NSIZE];
void init() {
scanf("%d %d %d", &M, &t, &N);
for (int i = 0; i < N; i++) {
Data c;
cin >> c.time >> c.pos;
c.idx = i;
if (c.pos == "left")L.push(c);
else R.push(c);
}
}
int main(void) {
init();
int time = 0;
while (R.size() + L.size() != 0) {
int flag = 0;
if (L.size()!=0&&L.front().time <= time) {
flag = 1;
if (pos == 'L') {
pos = 'R';
int cnt = 0;
while (L.size()!=0&&L.front().time <= time&cnt<M) {
finalTime[L.front().idx] = time + t;
L.pop();
cnt++;
}
time += t;
}
else {
time += t;
int cnt = 0;
while (L.size()!=0&&L.front().time <= time & cnt < M) {
finalTime[L.front().idx] = time + t;
L.pop();
cnt++;
}
time += t;
}
}
if (R.size()!=0&&R.front().time <= time) {
flag = 1;
if (pos == 'R') {
pos = 'L';
int cnt = 0;
while (R.size()!=0&&R.front().time <= time & cnt < M) {
finalTime[R.front().idx] = time + t;
R.pop();
cnt++;
}
time += t;
}
else {
time += t;
int cnt = 0;
while (R.size()!=0&&R.front().time <= time & cnt < M) {
finalTime[R.front().idx] = time + t;
R.pop();
cnt++;
}
time += t;
}
}
if (flag==0){
time++;
}
}
for (int i = 0; i < N; i++)cout << finalTime[i] << endl;
return 0;
}
|
처음에 맨날 처음에라고 시작으로 글을 시작을 하는데, 항상 처음 풀었을때가 상기가 됩니다.
잡담은 그만하고 이문제의 포인트는 무엇일까 생각을 해봅시다.
초기에 생각을 했을때 한공간에 담겨져있는 상태에서 시간을 계산해서 하려고 했었습니다.
하지만 이게 예제는 그게 통하지만 사실상 그렇게 하면 안되는 방식이였습니다. 물론 제가 잘못 이해
한 점이 있어서 그랬었지만 이문제는 제가 생각했을때 L에 도착하는 사람과 R과 도착하는 사람을 큐에 따로 담고
시간이된 경우에 현재 배의 위치가 어디인지 잘 저장하는게 가장 중요하고 그것을 중심으로 왔다갔다 해야하는지가
정해집니다.
이게 무슨 소리지 하나도 안 읽히는 분들을 위해
그림으로 설명해드리겠습니다.
약간 이런식으로 담아서 조건을 적절히 줘서 이동시키고 내리게 할떄 그때 시간 저장하는식으로 풀이를 하였습니다.
그림을 잘그려서 조건만 잘주면 쉬운문제라 생각합니다.
오늘은 여기까지이고 내일도 좋은 알고로 찾아뵙겠습니다.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 14226 이모티콘 (0) | 2019.10.03 |
|---|---|
| 백준 13549 숨바꼭질3 (0) | 2019.10.03 |
| 백준 2931 가스관 (0) | 2019.10.02 |
| 백준 16137 견우와 직녀 (0) | 2019.09.30 |
| 백준 4577 소코반 (0) | 2019.09.30 |
댓글