Sablog Models/알고리즘

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

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

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

문제의 단서는 여기에 있다.
주어진 논을 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[]을 '각 열에서 동생이 갖는 칸 수'라 정의했으므로,
출력할 때 형이 갖는 칸 수로 바꾸어야 한다.



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

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

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


너무 늦게.