백준 17143. 낚시왕

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

17143번: 낚시왕

 

이 문제는 상어를 이동시키는것이 핵심인 문제다. 

그런데 상어를 이동시킬때 생각해야할 부분들이 있다.

 

우선 상어를 이동시켰을때 최종적으로 같은 위치에 여러마리의 상어들이 있다면 그 중 가장 크기가 큰 상어만 남겨야한다.

만약 2차원 배열 하나를 기준으로 상어를 이동시킨다면 아직 이동시키지 않은 상어의 정보가 사라질수 있기 때문에 임시 2차원 배열을 하나 만들어서 그곳에 이동시켜야한다.

 

그리고 처음에 제출했을때 시간초과가 나왔는데 이유는 상어의 이동을 한칸 한칸 직접 이동 시켰기 떄문이다.

상어의 속도는 최대 1000이기 때문에 최악의 경우 모든 상어들이 1000의 속도를 갖고 있다면 상어들이 1초 움직일때마다 1000x100x100이 되고, 낚시왕이 최대 100칸 이동한다면 시간복잡도는 최악의 경우  O(1000x100x100x100) = O(10억)이 된다.

 

나는 상어를 이동시킬때 상어를 해당 방향으로 끝까지 한번에 이동시키고 남은 이동거리 만큼 반대로 이동시키는 방식으로 해결했다.

(이동해야하는 칸이 최대 1000이기 때문에 방향을 여러번 바꾸게 될 수도 있다)