1797: 고기잡이(L)
[만든사람 : onthebitLab-admin 2022/10/12]
문제 설명
우리나라 최고의 어부 정올이가 이번에 네모네모 배 고기잡이 대회에 참가한다.
이 대회에는 3개의 라운드가 있는데, 두 번째 라운드는 2차원 형태로 표현될 수
있는 작은 연못에서 길쭉한 그물을 던져서 최대한 많은 고기를 잡는 것이 목적이다.
1라운드의 예를 들면 연못의 크기가 1*6이고 물고기의 위치와 가치가 다음과 같다 고 하자. 1 0 2 0 4 3 여기서 그물의 크기는 1*3이라고 할 때, 잡을 수 있는 방법은 (1 0 2), (0 2 0), (2 0 4), (0 4 3)의 4가지 방법이 있다.
이 중 가장 이득을 보는 방법은 마지막 방법 0 + 4 + 3 = 7이다. 따라서 주어진 경우의 최대 이득은 7이 된다. 정올이는 최대한 가치가 큰 물고기를 잡아서 우승하 고 싶어 한다. 연못의 폭과 각 칸에 있는 물고기의 가치, 그물의 가로의 길이가 주어질 때, 잡을 수 있는 물고기의 최대이득을 구하는 프로그램을 작성하시오.
1라운드의 예를 들면 연못의 크기가 1*6이고 물고기의 위치와 가치가 다음과 같다 고 하자. 1 0 2 0 4 3 여기서 그물의 크기는 1*3이라고 할 때, 잡을 수 있는 방법은 (1 0 2), (0 2 0), (2 0 4), (0 4 3)의 4가지 방법이 있다.
이 중 가장 이득을 보는 방법은 마지막 방법 0 + 4 + 3 = 7이다. 따라서 주어진 경우의 최대 이득은 7이 된다. 정올이는 최대한 가치가 큰 물고기를 잡아서 우승하 고 싶어 한다. 연못의 폭과 각 칸에 있는 물고기의 가치, 그물의 가로의 길이가 주어질 때, 잡을 수 있는 물고기의 최대이득을 구하는 프로그램을 작성하시오.
입력 설명
입력 첫 번째 줄에 연못의 폭 N, M이 입력된다. 3.0514( N, M <= 100 인 자연수 )
두 번째 줄에 그물의 폭 W, H가 입력된다.
( W <= N, H <= M 인 자연수 )
세 번째 줄에 N*M개의 물고기의 가치가 공백으로 구분되어 주어진다.
각 물고기 의 가치는 7 이하의 자연수이다. 0일 경우에는 물고기가 없다는 의미이다.
두 번째 줄에 그물의 폭 W, H가 입력된다.
( W <= N, H <= M 인 자연수 )
세 번째 줄에 N*M개의 물고기의 가치가 공백으로 구분되어 주어진다.
각 물고기 의 가치는 7 이하의 자연수이다. 0일 경우에는 물고기가 없다는 의미이다.
출력 설명
출력 잡을 수 있는 물고기의 최대 가치를 출력한다.
입력 예시 Copy
2 6
1 3
1 0 2 0 4 3
3 4 0 2 0 1
출력 예시 Copy
7