문제 : https://www.acmicpc.net/problem/17143
17143번: 낚시왕
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.
www.acmicpc.net
문제 파악하기
낚시왕이 1열부터 C열까지 이동하면서 잡은 상어들의 크기를 모두 구하는 문제입니다. 낚시왕과 상어들은 일련의 단계에 맞춰 행동하며, 우리는 낚시왕과 상어들이 규칙에 맞게 움직일 수 있도록 알고리즘을 설계해야 합니다.
문제 해결하기
우선 가장 처음 단계는 낚시왕이 오른쪽으로 한칸 이동하여 해당 열에 있는 상어 중 땅과 가장 가까운 상어를 잡습니다. 이 경우, 우리는 상어 중 낚시왕과 같은 열에 있는 상어를 찾은 후, 그 중 가장 열의 값이 작은 상어를 찾아내야 합니다. 주어진 격자판의 크기가 크지 않기 때문에 단순히 모든 상어들의 위치를 탐색하여 손쉽게 해결할 수 있습니다.
다음으로 상어들의 위치를 이동시켜야 합니다. 상어들의 위치를 이동시키는 과정이 조금은 까다로운데, 무턱대고 s만큼 반복문을 돌리면 시간초과가 나올 수 있기 때문입니다. 따라서, 우리는 현재 위치와 s의 값 사이의 관계를 파악하여 수식을 세운 뒤, 다음 위치를 파악해야 합니다. 우선, s의 값을 줄여봅시다. 우리는 상어가 일정 횟수만큼 이동하면 원래 위치로 돌아온다는 점을 눈치챌 수 있습니다. 상어가 위/아래로 움직이는 경우에는 (C*2-2)번, 오른쪽/왼쪽으로 움직이는 경우에는 (R*2-2)번 움직이면 원래 위치로 돌아옵니다. 따라서 우리는 s의 값을 반복되는 횟수만큼으로 나눠 나머지를 구하면 s의 값을 줄일 수 있습니다.
이렇게 줄인 s의 값에서 나올 수 있는 경우의 수는 총 몇 가지일까요? 정답은 총 3가지 입니다.
(1) 벽에 닿지 않고 이동하는 경우 / (2) 벽에 1번 닿고 이동하는 경우 / (3) 벽에 2번 닿고 이동하는 경우는 경우
(1)번 경우는 간단합니다. 그대로 값을 이동시켜주면 됩니다. 문제는 (2)번과 (3)번인데 (2)번과 (3)번 과정을 처리하는 간단한 방법은 우선 상어를 가장 가까운 벽으로 이동시킨 후, 남은 이동 횟수를 비교하면 됩니다. 만약 남은 이동 횟수가 다음 벽까지 남은 거리보다 적은 경우, 해당 위치까지 이동시키고 상어가 바라보는 방향을 바꿔주면 됩니다. 만약 남은 이동 횟수가 다음 벽까지 남은 거리보다 많은 경우, 적절한 수식을 세워 이동시켜주고 방향은 그대로 유지시키면 됩니다.
2가지 단계를 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
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
#include <stdio.h>
#include <string.h>
#include <vector>
#define NMAX 105
#define INF 0x7FFFFFFF
using namespace std;
struct Shark {
int r, c;
int sp, d, sz;
};
int R, C, M;
int r, c, s, d, z;
int maps[NMAX][NMAX], death[NMAX*NMAX];
int tmp, tmpi, p, ret;
vector< Shark > inp;
// 자기자리로 돌아오는데 필요한 비용 : R*2-2 or C*2-2
void nxtMove(int idx) {
int t;
if(inp[idx].d<=2) t = inp[idx].sp%(R*2-2);
else t = inp[idx].sp%(C*2-2);
switch(inp[idx].d) {
// 위
case 1:
if(inp[idx].r - t > 0) inp[idx].r -= t;
else {
// 가장 가까운 벽으로 이동
t -= (inp[idx].r-1);
// 그대로 아래로 내려가기
if(t < R) {
inp[idx].r = t+1;
inp[idx].d = 2;
}
// 벽에 부딪힌 후 올라오기
else {
inp[idx].r = R - (1+t-R);
}
}
break;
// 아래
case 2:
if(inp[idx].r + t <= R) inp[idx].r += t;
else {
t -= (R-inp[idx].r);
if(t < R) {
inp[idx].r = R - t;
inp[idx].d = 1;
}
else {
inp[idx].r = t-R+2;
}
}
break;
// 오른쪽
case 3:
if(inp[idx].c + t <= C) inp[idx].c += t;
else {
t -= (C-inp[idx].c);
if(t < C) {
inp[idx].c = C-t;
inp[idx].d = 4;
}
else {
inp[idx].c = t-C+2;
}
}
break;
// 왼쪽
default:
if(inp[idx].c - t > 0) inp[idx].c -= t;
else {
t -= (inp[idx].c-1);
if(t < C) {
inp[idx].c = t+1;
inp[idx].d = 3;
}
else {
inp[idx].c = C - ((1+t)-C);
}
}
}
}
int main() {
// input
scanf("%d %d %d", &R, &C, &M);
for(int i=0;i<M;i++) {
scanf("%d %d %d %d %d", &r, &c, &s, &d, &z);
inp.push_back({r, c, s, d, z});
}
for(int pos=1;pos<=C;pos+ +) {
// 상어 잡기
tmp = INF;
for(int i=0;i<M;i++) {
if(!death[i] and inp[i].c == pos) {
if(inp[i].r < tmp) {
tmp = inp[i].r;
tmpi = i;
}
}
}
if(tmp != INF) {
death[tmpi] = 1;
ret += inp[tmpi].sz;
}
// 상어 이동
memset(maps, -1, sizeof(maps));
for(int i=0;i<M;i++) {
if(death[i]) continue;
nxtMove(i);
r = inp[i].r; c = inp[i].c;
p = maps[r][c];
if(p == -1) maps[r][c] = i;
else {
if(inp[p].sz > inp[i].sz) death[i] = 1;
else {
death[p] = 1;
maps[r][c] = i;
}
}
}
}
printf("%d", ret);
}
|
cs |
후기
상어들을 조건에 맞게 이동시키는데 살짝 헷갈릴 수 있지만 수 있지만 구현 자체는 나름 간단한 문제라고 생각합니다. 비슷한 유형으로 개미( https://www.acmicpc.net/problem/10158 ) 문제도 있으니 한번 풀어보길 추천합니다.
'문제 노트 > 백준' 카테고리의 다른 글
| 용량 확보( BOJ 9327 ) (0) | 2021.10.11 |
|---|---|
| 사과와 바나나( BOJ 3114 ) (0) | 2021.10.04 |
| 종이 접기( BOJ 1802 ) (0) | 2021.09.24 |
| 7-세그먼트 디스플레이( BOJ 18118 ) (0) | 2021.09.15 |
| K번째 수( BOJ 1300 ) (0) | 2021.09.10 |