시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 69 | 37 | 30 | 60.000% |
n × m 크기의 행렬이 있다. 이 행렬을 가로로 a번, 세로로 b번 잘라 (a + 1) × (b + 1) 개의 부분으로 분할하려고 한다. 이 때, 같은 부분을 두 번 이상 자를 수는 없다. 즉, 한 개의 원소도 포함되지 않은 부분은 존재할 수 없다.
그림 1 | 그림 2 |
위 그림 1과 같은 6 × 7 행렬이 있을 때, 이 행렬을 가로로 2번, 세로로 3번 자르면 그림 2와 같이 된다.
분할의 '점수' 는 잘라진 각 부분의 합들 중에서 가장 큰 값으로 정의한다. 예를 들어, 그림 2와 같은 분할에서의 점수는 색칠한 부분의 합인 19이다. 최소로 분할하면 점수는 15이고, 그림은 생략한다.
행렬이 주어졌을 때 가능한 최소 점수를 구하는 프로그램을 작성하시오.
첫 번째 줄에 자연수 n(2 ≤ n ≤ 100)과 m(2 ≤ m ≤ 8)의 값이 주어진다. 두 번째 줄에는 자연수 a(1 ≤ a < n), b(1 ≤ b < m) 의 값이 주어진다. 세 번째 줄부터 차례로 n개의 줄에는 행렬의 원소들이 공백으로 구분되어 주어진다. 행렬의 모든 원소들은 100,000 이하의 자연수이다.
첫 번째 줄에 최소 점수를 출력한다.
6 7 2 3 4 1 3 4 2 1 2 1 2 2 5 7 1 4 1 5 4 2 8 2 3 2 1 1 2 2 2 6 3 3 3 2 4 1 7 1 1 4 7 6 1 1
15