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

이 포스트에서는 지난번에 올린 소스 코드가 어떤 식으로 구성되었는지 설명해 보겠다.
(참 빨리 올린다...=_=;)

사실 문제를 풀 만한 사람이라면 설명할 필요조차 없는 문제와 코드였다.

문제의 단서는 여기에 있다.

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

문제에서는 이것이 제약조건처럼 나왔다.

하지만 만약 이 조건이 없다면 최적의 조건을 찾기 위해서는,
프로그램은 위-아래로 나누는 모든 경우를 읽어야 한다.
만약 그렇다면 1열을 1개, 2개, …, n개까지 나누는 각각에 대해 2열을 1개, 2개, …, n개까지 나누고,
그런 작업을 n열에 이르기까지 했어야 한다.

각 열마다 동생에게 할당되는 칸(위에서부터 셈)의 수를 solution[n]이라고 하면,
각 solution[i]에 대해 0 <= solution[i] <= n (0 <= i < n)이므로

solution := best of {
    (0, 0, …, 0, 0),    (0, 0, …, 0, 1),    …,    (0, 0, …, 0, n),
    (0, 0, …, 1, 0),    (0, 0, …, 1, 1),    …,    (0, 0, …, 1, n),
    …,
    (0, 0, …, n, 0),    (0, 0, …, n, 1),    …,    (0, 0, …, n, n),
…,

    (n, n-1, …, 0, 0),    (n, n-1, …, 0, 1),    …,    (n, n-1, …, 0, n),
    (n, n-1, …, 1, 0),    (n, n-1, …, 1, 1),    …,    (n, n-1, …, 1, n),
    …,
    (n, n-1, …, n, 0),    (n, n-1, …, n, 1),    …,    (n, n-1, …, n, n),

    (n, n, …, 0, 0),    (n, n, …, 0, 1),    …,    (n, n, …, 0, n),
    (n, n, …, 1, 0),    (n, n, …, 1, 1),    …,    (n, n, …, 1, n),
    …,
    (n, n, …, n, 0),    (n, n, …, n, 1),    …,    (n, n, …, n, n) }

이 nⁿ가지의 경우를 모두 훑어야 하는 대참사가 발생하는 것이다.
(물론 프로그램을 짜는 데 있어서 쉬워지지만, 시간을 고려해야 할 수 있다.)

대신, 위의 제약조건은 위에서 탐색해야 할 경우를 아래와 같이 줄인다.

solution[i + 1] <= solution[i] (i > 0)

(solution 배열을 각 열에서 동생이 가져갈 칸 수로 가정했기 때문에 나오는 식이다.)

---

실제 소스 설명은 함수별로 나눈다.

int main()

main() 함수는 수확량 행렬을 입력받는 루틴, 문제를 푸는 루틴, 결과를 출력하는 루틴을 호출한다.
0을 반환하고 끝난다.

void tablein()

tablein() 함수는 포스트 (3)-1 에서 이미 대략적인 설명을 마쳤다.
다만, 흔히 그러듯, 인수로 넘겨줘야 할 것이 워낙 많아서 일부는 전역변수로 빼냈다.
table[i][j]에서 i가 행 번호, j가 열 번호이다.
diff_best (최적의 경우 형과 동생의 수확량 차이)를 total로 초기화한다.

void divide(char col)

divide() 함수는 말 그대로 나누기만 하는 함수이다.
위에서 설명한 solution[i + 1] <= solution[i]의 원칙을 따라 모든 경우를 순차 탐색한다.
divide(i)가 입력되면 solving[i]를 0부터 solving[i-1]까지 늘려 가며 divide(i+1)을 호출하고,
n번째 열을 세고 있는 경우 각 테스트 케이스에 대해 기존의 답보다 최적에 가까운지 점검한다.
최적에 가까운지 점검하는 부분은 checknow()로 뺐다.

void checknow()

checknow() 함수는 '현재까지 구해진 해 중에서 최적의 해'와 '현재의 해'를 비교한다.
현재까지 구해진 해 중 최적의 해는 그 경우 형과 동생이 갖는 수확의 차이로 저장되며,
현재의 해가 최적에 더 가까운 경우 solving[]이 우선 해가 된다.
동생이 갖는 수확을 구하는 함수 upppersum()을 호출한다.
형과 동생이 갖는 수확의 차이에서 abs() 함수를 쓰기 위해 <math.h>를 #include시켰다.
solving[]이 최적에 더 가까운 해로 판별되는 경우 makesol()을 호출한다.

void makesol()

makesol() 함수는 solving[]을 solution[]에 복사하고 현재 형과 동생의 차이를 저장한다.
memcpy() 함수를 쓰기 위해 <stdlib.h>를 #include시켰다.

int uppersum()

uppersum() 함수는 solving[]에 의해 나누었을 때 동생이 갖는 수확을 계산하여 반환한다.

void finish()

finish() 함수는 diff_best와 solution[]에 의한 최적의 해를 구한다.
다만 프로그램 전체에서 solution[]을 '각 열에서 동생이 갖는 칸 수'라 정의했으므로,
출력할 때 형이 갖는 칸 수로 바꾸어야 한다.



별로 잘 짜이지도 않은 소스 코드 설명은 여기서 마친다.

프로그래밍을 할 때마다 함수를 어떻게 기능별로 나눌지 스펙 짜듯 생각했는데,
이번에는 그냥 손 가는 대로 함수를 나눌 수 있었다.

어쩌면 생각하는 기능마다 따로 빼서 하나의 함수를 하나의 작은 부품으로 만드는 것이...
장기 프로젝트뿐만 아니라 대회에서 작은 아이디어를 잡는 데도 유리할 수 있다는 것을 깨달았다.


너무 늦게.