[BOJ C++] 17143 낚시왕

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

17143번: 낚시왕

 

 

문제 이해

RxC 크기의 격자 판이 주어지고 해당 격자에는 상어들이 존재 합니다. 상어들은 각각의 이동방향으로 움직이고 벽을 만나게 되면 진행방향을 반대로 돌려 이동합니다. 이동이 끝났을 때 겹치는 상어가 있다면 더 큰 상어가 작은 상어를 잡아먹게 되고, 낚시왕이 한칸씩 이동할 때마다 y열에서 가장 가까운 상어 하나씩을 잡을 수 있습니다. 낚시왕이 잡은 상어들의 크기의 합을 구하는 문제였습니다.

 

 

입출력 조건

시간초 제한은 1초였고, 격자 크기는 최대 100x100 입니다.

 

 

풀이

처음에는 단순히 구현하였습니다. 최대 1만 마리의 상어가 있고 마리당 최대 1000칸 이동할 수 있으니 반복문을 돌려도 1000만 이면 수행이 완료될거라 생각했습니다. 하지만 낚시왕도 최대 100칸까지 이동할 수 있어 1000만 * 100이 되어 10억이 되어 시간초과가 뜰 수 있었습니다. 그래서 규칙상 상하는 (R-1) * 2, 좌우는 (C-1) * 2이면 원상태로 복귀되기에 그것들로 나누어 해결하였습니다.

단순 구현이므로 아래 전체코드를 확인해 주시면 감사하겠습니다.

 

 

에러 및 느낀 점

시간 복잡도 계산을 좀 잘해야 할 거 같습니다..

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/17143_%EB%82%9A%EC%8B%9C%EC%99%95.cpp

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.