[APS] 백준 17143. 낚시왕 C++ 풀이

 Gold II  https://www.acmicpc.net/problem/17143

17143번: 낚시왕

 

 

 Problem 

1. R×C 크기의 격자판에서 낚시왕이 상어 낚시를 한다. 칸에는 상어가 최대 한 마리 들어있을 수 있고, 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음 1번 열의 한 칸 왼쪽에 있다.
2. 1초 동안 아래에 적힌 일이 순서대로 일어난다.
   1) 낚시왕이 오른쪽으로 한 칸 이동한다.
   2) 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
   3) 상어가 방향과 속도에 따라 이동한다. 이 때, 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한 채로 이동한다. 한 칸에 상어가 여러 마리 존재하는 경우 가장 큰 상어만 남는다.
3. 낚시왕이 잡은 상어 크기의 합을 구한다.

 

 

 Solution 

문제에 그림 많고 시뮬레이션하는, 제가 좋아하는 유형의 문제라서 되게 재미있게 풀었습니다.

먼저, 각 상어의 위치, 속력, 방향, 크기를 가지고 있는 상어 구조체를 만들었습니다. 낚시터의 각 칸마다 상어를 넣습니다. (저는 pop, push 연산을 편하게 하려고 벡터를 사용했지만, 굳이 벡터를 사용하지 않아도 됩니다.. ㅎㅎ) 그 뒤는 문제에서 시키는 대로 구현해주면 되는데, 처음에는 상어의 위치를 바꿀 때 상어의 속력만큼 while문을 돌리면서 한 칸씩 이동하는 식으로 구현해서 시간 초과를 받았습니다. (낚시왕은 100번 이동 가능하고, 상어의 개수는 총 10000마리까지 가능한데, 속력인 s가 1000까지 가능하다보니 당연히 시간 초과..😂)

생각해보니 위, 아래 방향으로 움직이는 상어의 경우 속력이 (R - 1) * 2배일 때, 좌우로 움직이는 상어의 경우 속력이 (C - 1) * 2배 일 때 같은 자리의 똑같은 방향으로 돌아오게 됩니다. 따라서 처음 상어의 속력을 저장할 때 최소의 경우만 생각할 수 있도록 방향에 따라 (R - 1) * 2 또는 (C - 1) * 2로 나눈 나머지를 속력으로 저장해서 시간 초과 문제를 해결했습니다. 이 부분이 해당 문제를 푸는 키포인트겠네요.

정리하자면 아래와 같습니다.

 

1. 상어가 원래 자리로 돌아오는 경우를 제외하고 최소의 이동거리만 저장한다.
2. 낚시왕을 이동시키고 해당 거리에서 제일 가까운 거리의 상어를 잡은 뒤(pop_back) 답에 더해준다.
3. 벡터에 상어가 존재할 경우 pop해주고, 상어의 속력만큼 while문을 돌리면서 다음 위치를 찾는다.
4. 다음 위치에 상어가 있을 경우, 크기를 비교해서 현재 상어가 크기가 더 큰 경우 상어를 바꿔주고, 현재 상어가 더 작으면 현 상태를 유지한다. 상어가 없는 경우 현재 상어를 바로 넣는다.
5. 2~4 과정을 낚시왕이 열의 가장 끝 부분에 도착할 때까지 반복한다.

 

 

 Code