멤고리즘 3회 3번. 술잔 나누기

문제

오늘은 멤버십 회식 날이다.

멤버십 회원들은 운영자님을 사랑하는 마음을 담아 N * N 개의 술잔에 술을 따라 두었다.

각 회원이 운영자님을 사랑하는 마음이 다르기에 술잔의 술의 양도 다양하다.

큰 운영자님과 작은 운영자님은 사이가 좋기 때문에 총 마시는 술의 양의 차이가 되도록 적게 하여 마시고 싶어 한다.

그런데 술을 마시다 보면 정신이 없기 때문에 규칙을 정해 놓았다.

N * N 개의 술잔들을 두 부분으로 나누어, 큰 운영자님은 위 쪽의 술을 마시고 작은 운영자님은 아래쪽의 술을 마시기로 하였다.

이 때 각 운영자님에게 배분된 구역이 단조 증가하는 계단 모양이 되게 하려고 한다. 즉, 주어진 술잔 들을 N * N 행렬로 볼 때 작은

운영자님이 특정 열에서 할당받는 구역의 개수는 바로 왼쪽 열에서 받은 구역의 개수보다 크거나 같아야 한다.

 

 

 

예를 들어, 다음 세 개의 그림 중 그림 1과 2는 올바른 배정 방법으로, 회색 지역은 작은 운영자님이 마셔야 할 술잔, 흰 부분은 큰 운영자님이 마셔야 할 술잔이다. 그러나 그림 3은 술잔을 나누는 규칙을 어기는 경우이다.

 

입력

첫째 줄에 N (2<=N<=20) 이 주어지고, 이어서 N * N 행렬로 각 술잔에 따라진 술의 양이 0 에서 100 사이의 정수로 주어진다.

출력

첫째 줄에 최적의 방법으로 영역을 나누었을 때, 총 마시는 술의 양의 차이의 최소값을 출력한다.

 

예제 입력1​

5
3 4 5 1 8
8 2 3 2 2
0 2 9 5 4
1 11 3 0 5
4 5 2 7 1

예제 출력1

1

출제자 : 안일규