문제
후삼국을 통일한 고려의 태조 왕건은 전공을 세운 장수들에게 점령한 지역의 토지를 나누어 주기로 하였다. 토지는 N × M 크기의 직사각형 모양이며 N × M의 격자모양으로 나누었을때 각각의 위치마다 농사를 지어서 얻을 수 있는 생산량을 알 수 있다.
그림1 은 5 × 6인 토지의 각 위치에서 얻을 수 있는 생산량을 나타낸 예이다.
토지를 나누는데에는 많은 비용이 들기 때문에 간단하게 가로를 X개로 분할하고 세로를 Y개로 분할하여 X × Y명의 장수에게 토지를 나누어 주려고 한다. 태조 왕건은 생산량이 너무 적은 곳을 배정받은 장수가 불만을 품고 역모를 꾸미지 않을지 무척 걱정이 되었다. 그래서 가능하면 생산량의 합이 가장 적은 부분의 합계가 최대가 되도록 분할하려고 한다.
그림2는 가로를 2개로 세로를 3개로 분할한 것이다. 이때 생산량의 합이 가장 적은 곳은 색칠한 부분으로 11이다.
각 구역별 생산량의 정보와 가로와 세로로 분할하려는 개수가 주어질 때 생산량의 합이 가장 적은 곳이 최대가 되도록 분할하여 그 값을 출력하는 프로그램을 작성하시오
입력
첫 번째 줄에 자연수 4개가 주어지는데 토지의 크기 N( N ≤ 20 )과 M( M ≤ 20 ), 가로와 세로의 분할개수 X( X ≤ N ), Y( Y ≤ M )의 값이다. 두 번째 줄부터 차례로 N개의 줄에는 각 위치에서 얻을 수 있는 생산량이 주어지며 생산량은 모두 20 이하의 자연수이다.
<제약조건> 전체 데이터의 30%는 N,M ≤ 10, X,Y ≤ 3 이다.
출력
첫 번째 줄에 생산량의 합이 최소인 부분의 값이 최대가 되도록 분할 했을 때, 최소부분의 생산량의 합을 출력한다.
예제
5 6 2 3
1 5 3 7 5 3
6 3 5 1 2 4
5 8 2 3 3 9
5 2 1 8 4 1
1 3 9 2 2 4
14
로그인해야 코드를 작성할 수 있어요.