오래전에 풀어봤다가 포기한 문제였는데, 이번에 역시 어렵게 풀었다.
n의 범위가 10000인 n * n 영역에서 (이미 배열을 잡을 수 없다는 것을 캐치)
l ( 4 <= l <= 100)길이의 그물을 쳐서
m(1 <= m <= 100)개의 물고기를 최대로 가져오게 할 때
그 물고기 어획량이 최대가 되는 마리 수를 계산하는 문제였다.
그물은 우측으로, 아래쪽으로 칠 수 있다는 조건이 희망적이었다.
우선 대충 문제만 봐도 토가 나오는 문제였지만, 겁먹은 점도 많은 것 같다.
이번에 느낀 문제 접근 방법은
[1] 규칙이 있나?
[2] 완전탐색 가능한가?
[3] 완전히 탐색하는데, 범위를 현저히 줄일 수 있는가?
이다.
1번은 모르겠고, 2번은 안되었고, 3번의 방법을 적절히 선택해서 풀어야 하는 문제였다.
맨 처음에는 문제 예시의 그림을 보고
물고기 위치보다 그물을 쳐보면 되잖아? 개쉽네 이랬는데
다음의 예외를 생각 못했었다.
위와 같은 경우 물고기 좌표가 있지 않은 곳에서 그물을 쳐야 최대를 수확할 수 있다.
그 다음 생각한 방법은 물고기의 입력 범위의 x, y의 최대 최소
4개의 값을 받아와서
그 범위만큼 완전 탐색하는 것이었다.
이 방법은 시간 초과가 났다.
마지막 방법은 내가 완벽히 생각해내진 못 했다.
이렇게 하는 것이다.
x좌표, y좌표를 각각 따로따로 sorting 한 후에
그 좌표들을 이중 포문 돌리면서 탐색하니까 답이 나왔다.
머리를 잘 굴려서 최대한 범위를 적게 하는 팁이 필요한 문제였다.
실행 시간은 망이었지만..
어쨋든 꿀팁, x좌표, y좌표 정렬한 후에 완전탐색
