상어 낚시하는 낚시왕이 정해진 규칙에 따라 움직이는 상어 중 잡을 수 있는 상어의 크기의 합을 구하는 문제입니다. 이건 딱히 풀이라고 할 게 없습니다. 먼저 주어진 보드 크기에 맞게 상어의 정보를 저장하는 배열을 두 개 만듭니다. 하나는 현재, 하나는 다음을 나타냅니다. 이제 상어 정보를 입력받아 현재 배열의 알맞은 위치에 상어 정보를 추가합니다. 그리고 매 초 낚시되는 상어를 찾아 삭제한 다음, 모든 상어에 대해 다음을 나타내는 배열에 올바른 정보를 업데이트해줍니다. 여기서 하나 구현하기 까다로울 수 있는 것은 방향과 속력에 따른 상어의 다음 위치인데, 여기서 쓰이는 아이디어는 다음과 같습니다.
음의 방향으로 움직이는 상어는 양의 방향 끝에 거울이 있다고 생각하고 상어가 L과 2L 사이의 가상 공간에 존재하며 양의 방향으로 움직이는 것으로 간주한다. (L은 이동축의 길이)
이렇게 하면 나머지 연산을 활용하여 다음 위치를 쉽게 구할 수 있습니다. 이를 활용하여 다음 상어의 위치를 $O(RC)$에 구할 수 있습니다. 결과적으로 $O(RC^2)$에 문제가 원하는 답을 구하여 출력할 수 있습니다.
PS알못 OrbitHv의 PS