17143 낚시왕

2019 삼성전자 DS SW 기출문제

2차원 시뮬레이션 문제

 

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

https://github.com/surinoel/boj/blob/master/17143.cpp

 

 

[+수정] 재채점 결과 시간초과가 나왔다. 계속 들여다본 결과, 속력의 최댓값이 1000이기 때문에 최악의 경우 시간복잡도는 열의갯수*상어의갯수*최대속력 = 100 * 10000 * 1000 = 10억으로 해결할 수 없다. 속력의 경우에는 방향에 따라서 달라지겠지만 2 * ((행/열) - 1)을 이동하면 자기 자신의 위치와 방향을 그대로 갖게 된다. 따라서 이 점을 이용해서 나머지 연산으로 1000을 약 200으로 줄일 수 있다. 상어의 갯수가 지속적으로 감소한다는 점을 이용하면 충분히 시간 안에 해결할 수 있는 로직이 된다