어떤 N × N 개의 단위 구역으로 구성된 논이 있다.

각 단위 구역에서는 쌀이 생산되는데 구역에 따라서 쌀의 생산량이 다르다.

아래는 5 × 5 = 25개의 단위 구역으로 나누어진 논을 보여주고 있다.

각 구역에 적혀 있는 숫자는 예상되는 쌀의 수확량(가마)이다.

두 의좋은 형제는 이 N × N의 논을 다음과 같이 두 부분으로 나누어 형은 아래쪽에 있는 땅을 가지고, 동생은 위쪽의 땅을 가지기로 하였다.

전체 구역을 마구잡이로 나누면 기계로 농사를 짓는데 불편하기 때문에 각 형제에게 배분된 구역이 단조 증가하는 계단 모양이 되게 하려고 한다.

즉, 주어진 논을 N × N 행렬로 볼 때 형이 특정 열에서 할당받는 구역의 개수는 바로 왼쪽 열에서 받은 구역의 개수보다 크거나 같아야 한다.

예를 들어 다음 세 그림 중 그림 1과 2는 올바른 배정 방법으로, 회색 지역은 형의 논, 나머지 부분은 동생의 논이다.

그러나 그림 3은 논을 나누는 규칙을 어기는 경우이다.

두 형제는 논을 공평하게 나누기 위해, 위와 같은 방법들 중 각 영역의 예상 수확량의 차이가 되도록 적게 하고자 한다.

예를 들어 그림 1은 형의 예상 수확량이 48, 동생이 49로 최적인 경우이나, 그림 2는 형은 39, 동생은 58로 공평하게 나눠지지 않은 경우이다.

주어진 논을 최대한 공평하게 나누는 방법을 구하는 프로그램을 작성하라.

의좋은 형제 timer 1초 memory 512MB

의좋은 형제 1초 512MB