본문 바로가기

알고리즘

라이캣의 그물 한 번

New Era · 15번Lv. 2구간 합

라이캣의 그물 한 번

문제 설명

대리인 No.1의 기록 중에서

라이캣에게서 짧은 편지가 왔다. 원석을 나눠 주고 혼자 바다로 나가 낚시를 했다고 한다. 흔들리지 않는 마음을 되찾으려고 처음 생선을 잡던 때로 돌아갔다는 것이다. 편지 끝에는 바다 지도와 함께 "그물을 딱 한 번만 던질 거라면 어디에 던져야 했을까냥?"이라는 질문이 적혀 있었다. 우리 대리인들이 계산해 보기로 했다냥.

라이캣의 바다 지도는 n행 m열 격자이고, 각 칸에는 그 칸에 있는 물고기 수가 적혀 있습니다. 라이캣의 그물은 K×K 칸 크기의 정사각형입니다.

  • 그물은 격자 칸에 딱 맞게, 가로·세로 방향 그대로(돌리지 않고) 던집니다.
  • 그물 전체가 지도 안에 들어가야 합니다.
  • 그물에 덮인 K×K 칸의 물고기를 모두 잡습니다.

바다 지도와 K가 주어질 때, 그물을 한 번 던져 잡을 수 있는 물고기 수의 최댓값을 반환하는 solution 함수를 작성해 주세요.


제한 사항

  • data는 [바다 지도, K] 형태입니다.
  • 1 ≤ n(행 수), m(열 수) ≤ 300이고, 모든 행의 길이는 m으로 같습니다.
  • 0 ≤ 각 칸의 물고기 수 ≤ 9 (정수)
  • 1 ≤ K ≤ min(n, m)
  • 지도가 크고 그물도 크면, 그물을 놓을 때마다 K×K 칸을 하나하나 더하는 방법은 시간이 오래 걸립니다.

입출력 예

입력출력
[[[1, 0, 3, 2], [4, 2, 0, 1], [0, 5, 1, 3]], 2]11
[[[2, 7, 1], [0, 3, 9], [8, 4, 6], [5, 1, 2]], 3]40
[[[0, 0, 4, 0, 0], [1, 9, 2, 0, 7], [0, 3, 0, 6, 8]], 1]9

입출력 설명

입출력 예 #1

  • 3×4 바다에 2×2 그물을 던지는 자리는 6곳입니다. 각 자리에서 잡는 물고기 수는 아래와 같습니다(그물 왼쪽 위 칸 기준).
왼쪽 위 칸덮는 칸의 물고기합
0행 0열1, 0, 4, 27
0행 1열0, 3, 2, 05
0행 2열3, 2, 0, 16
1행 0열4, 2, 0, 511
1행 1열2, 0, 5, 18
1행 2열0, 1, 1, 35
  • 가장 많이 잡는 자리는 1행 0열이고, 답은 11입니다.

입출력 예 #2

  • 4×3 바다에 3×3 그물은 02행에 던지거나 13행에 던질 수 있습니다. 각각 40마리, 38마리이므로 답은 40입니다.

입출력 예 #3

  • 1×1 그물은 한 칸만 덮으므로 물고기가 가장 많은 칸(1행 1열, 9마리)에 던집니다.

예시 테스트

#입력기대값
1[[[1, 0, 3, 2], [4, 2, 0, 1], [0, 5, 1, 3]], 2]11
2[[[2, 7, 1], [0, 3, 9], [8, 4, 6], [5, 1, 2]], 3]40
3[[[0, 0, 4, 0, 0], [1, 9, 2, 0, 7], [0, 3, 0, 6, 8]], 1]9

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 12개도 함께 채점해요.