2009 정보올림피아드 지역본선 문제 Review (3)-1

3번 문제는 처음 보고 정체를 알 수 없었다.

의좋은 형제

  어떤 N × N 개의 단위 구역으로 구성된 논이 있다. 각 단위 구역에서는 쌀이 생산되는데 구역에 따라서 쌀의 생산량이 다르다. 아래는 5 × 5 = 25개의 단위 구역으로 나누어진 논을 보여주고 있다. 각 구역에 적혀 있는 숫자는 예상되는 쌀의 수확량(가마)이다.

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

  두 의좋은 형제는 이 N × N의 논을 다음과 같이 두 부분으로 나누어 형은 아래쪽에 있는 땅을 가지고, 동생은 위쪽의 땅을 가지기로 하였다. 전체 구역을 마구잡이로 나누면 기계로 농사를 짓는데 불편하기 때문에 각 형제에게 배분된 구역이 단조 증가하는 계단 모양이 되게 하려고 한다. 즉, 주어진 논을 N × N 행렬로 볼 때 형이 특정 열에서 할당받는 구역의 개수는 바로 왼쪽 열에서 받은 구역의 개수보다 크거나 같아야 한다. 예를 들어 다음 세 그림 중 그림 1과 2는 올바른 배정 방법으로, 회색 지역은 형의 논, 나머지 부분은 동생의 논이다. 그러나 그림 3은 논을 나누는 규칙을 어기는 경우이다.
  두 형제는 논을 공평하게 나누기 위해, 위와 같은 방법들 중 각 영역의 예상 수확량의 차이가 되도록 적게 하고자 한다. 예를 들어 그림 1은 형의 예상 수확량이 48, 동생이 49로 최적인 경우이나, 그림 2는 형은 39, 동생은 58로 공평하게 나눠지지 않은 경우이다. 주어진 논을 최대한 공평하게 나누는 방법을 구하는 프로그램을 작성하라.
  실행 파일의 이름은 BRO.EXE로 한다. 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.
 

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

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

그림 2

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

그림 3

입력 형식
  입력 파일의 이름은 INPUT.TXT로 한다. 첫째 줄에 논의 크기를 나타내는 정수 N (2≤N≤20)이 주어진다. 둘째 줄부터 N+1번째 줄에는 각 단위 구역의 예상 수확량이 0에서 100 사이의 정수로 주어진다. 둘째 줄에는 논의 제 1행의 각 구역의 예상 수확량에 해당하는 N개의 정수가 빈칸을 사이에 두고 주어지며, 셋째 줄에는 제 2행의 각 구역의 예상 수확량에 해당하는 N개의 정수가 빈 칸을 사이에 두고 주어진다. 넷째 줄부터 N+1번째 줄도 같은 형식으로 각 줄마다 N개 정수들이 주어진다.

출력 형식
  출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄에는 최적의 방법으로 영역을 나누었을 때의 예상 수확량 차이를 나타내는 정수를 출력하고, 둘째 줄에는 이 최적의 방법에서 논의 첫 번째 열부터 N번째 열까지 형이 배분받는 구역의 수를 나타내는 N개의 정수를 빈칸을 사이에 두고 출력한다. 방법이 여러 개인 경우 하나만 출력한다.

입력과 출력의 예

입력 (INPUT.TXT)

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

출력 (OUTPUT.TXT)

1
2 2 2 3 3

3번에서 드디어 알고리즘(?=알고리듬)을 짜야 하는 문제가 출현했다.


이 문제에서 n*n 구역으로 된 정사각형 논을 둘로 나눌 조건은 두 가지이다.
1. 왼쪽에서 오른쪽으로 올라가는 계단형으로 나눌 것.
2. 나뉜 두 부분에서 예상 수확량이 가장 비슷하게 (같을 수 있다면 같게) 할 것.


그래서 난 이런 식으로 프로그램을 짜기로 했다.

1) 논의 최대 크기는 20*20이고 예상 수확량은 음이 아닌 100 이하 정수이다.

int size, i, j;
char table[20][20]; //메모리를 아껴 보자는 심산

2) 모조리 입력받자. 총합의 절반에 가깝게 분할해야 하니 총합도 구하자.

int sect, total = 0;
FILE *fp = fopen("INPUT.TXT", "r");
fscanf(fp, "%d", &size);
for ( i = 0; i < size; i++ )
    for ( j =  0; j < size; j++ )
    {
        fscanf(fp, "%d", &sect);
        total += sect;
        table[i][j] = sect;
    }

3) 문제는 아래쪽을 기준으로 설명하고 있으나, 위에서 나누든 밑에서 나누든 결과는 같다.

차이는: 위쪽에서 볼 때 인접한 왼쪽 줄은 항상 오른쪽 줄보다 크거나 같아야 한다는...(;;)

그 대신 밑에서 새는 것보다 계산이 훨씬 수월하다.

왼쪽 줄을 1부터 늘리면서, 각 줄은 인접한 왼쪽 줄보다 작거나 같은 동안 늘리는 것이다.

그렇게 선택된 위쪽 구역의 넓이를 계산한다.

그런데 매 줄마다 수행해야 하는 문제는? -> 함수로 분해해서 스택을 사용하자.

그리고 각 함수는 절반을 넘어가는 순간 중단하고 최선의 상태 기억.



이 문제를 대회에서 직접 풀지는 못했지만 나름대로 솔루션을 제시해 봤다.

자세한 소스는 다음에...