1139: 영덕대게와 울진대게2
[만든사람 : 2022SFPC경북]
문제 설명
경북 울진군 후포면 후포리에서 동쪽으로 23km 떨어진 바다에 왕돌초라고 불리는 수중 암초가 있다. 왕돌초 근처에는 대나무처럼 곧은 다리를 가진 ‘대게’가 많이 서식하고 있는데, 영덕 어민이 잡아 강구항에서 판매하면 영덕대게, 울진 어민이 잡아 후포항에서 판매하면 울진대게라고 부른다.
대게 잡이 어민들은 그물을 던져 대게를 잡는데 어획량을 늘리기 위해 어군탐지기를 사용한다. 어군탐지기는 해수면에서 수직 방향으로 내려다본 바닷속 대게의 수를 격자로 구분하여 보여준다. 격자의 크기는 1 * 1이다.
어군탐지기에 나타난 n * n 크기의 영상에서 바닷속 대게의 수가 주어질 때, m * m 크기의 그물을 한 번 던져 최대 몇 마리의 대게를 잡을 수 있는지 출력해 보자.
대게 잡이 어민들은 그물을 던져 대게를 잡는데 어획량을 늘리기 위해 어군탐지기를 사용한다. 어군탐지기는 해수면에서 수직 방향으로 내려다본 바닷속 대게의 수를 격자로 구분하여 보여준다. 격자의 크기는 1 * 1이다.
어군탐지기에 나타난 n * n 크기의 영상에서 바닷속 대게의 수가 주어질 때, m * m 크기의 그물을 한 번 던져 최대 몇 마리의 대게를 잡을 수 있는지 출력해 보자.
입력 설명
첫 번째 줄에는 어군탐지기 영상의 한 변의 길이(n)와 그물의 한 변의 길이(m)가 스페이스로 구분되어 입력된다.
두 번째 줄부터 바닷속 대게의 수가 스페이스와 줄바꿈으로 구분되어 입력된다.
[2 <= n <= 500]
[2 <= m <= 500]
두 번째 줄부터 바닷속 대게의 수가 스페이스와 줄바꿈으로 구분되어 입력된다.
[2 <= n <= 500]
[2 <= m <= 500]
[m <= n]
[0 <= 격자 하나 당 대게의 수 <= 1,000] 출력 설명
그물을 한 번 던져 최대 몇 마리의 대게를 잡을 수 있는지 출력한다.
입력 예시 Copy
4 2
3 8 9 1
2 7 3 4
6 3 8 7
5 4 1 2
출력 예시 Copy
27