문제 링크
- http://icpc.me/7573
문제 출처
- 2013 지역 본선 중등2
시간복잡도
- O(n3)
풀이
완전 탐색은 시간 초과가 뜨기 때문에 다른 방법을 찾아야 합니다.
그물에서 이웃한 모서리에 두 마리의 물고기가 걸쳐지게 하는 방식으로 탐색하면 O(m^3)으로 해결 가능할 것 같습니다.
- 그물에 걸릴 물고기의 수를 계산하는 calc라는 함수를 만듭니다.
- n, l, m을 입력 받습니다.
- 물고기의 위치를 입력 받습니다.
- 물고기 중에서 2개를 고른 후, 그 두 물고기가 그물에서 이웃한 모서리에 걸쳐지게 그물을 이동한 후, calc 함수로 계산합니다.
- 3번 항목을 m^2번 반복합니다.
전체 코드
1 |
|