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

지난번에 문제를 3번까지 올리다 만 사실조차 까먹고 말았다가 이제 깨달았다.
알고 보니 내 컴퓨터에도 문제를 풀어 놓은 소스가 없었다.
(난 뭐-_-지 ㅜㅠ)

시험기간 중간에 낀 주말이지만, 무시하고 지나가기에는 너무 큰 문제라서 손을 대기로 했다.

그리고 코딩 따위를 금방 끝냈다.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

char table[20][20];
char solution[20], solving[20];
int total = 0;
int size;
int diff_now, diff_best;

void tablein();
void divide(char col);
void checknow();
void makesol();
int uppersum();
void finish();

int main()
{
    tablein();
    divide(0);
    finish();
    return 0;
}

void tablein()
{
    int i, j;
    int sect;
    FILE *fp;
    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;
        }
    }
    fclose(fp);
    diff_best = total;
}

void divide(char col)
{
    for (solving[col] = 0; col == 0 ? solving[col] <= size : solving[col] <= solving[col - 1]; solving[col]++)
    {
        if (col == size - 1)
            checknow();
        else
            divide((char)((int)col + 1));
    }
}

void checknow()
{
    if (total % 2 == 0)
        diff_now = abs(uppersum() - total / 2);
    else
        diff_now = abs(uppersum() - total / 2) + 1;
    if (diff_now < diff_best)
        makesol();
}

void makesol()
{
    diff_best = diff_now;
    memcpy(solution, solving, sizeof(char) * size);
}

int uppersum()
{
    int i, j, rets = 0;
    for (i = 0; i < size; i++)
        for (j = 0; j < solving[i]; j++)
            rets += table[j][i];
    return rets;
}

void finish()
{
    int i;
    FILE *fp = fopen("OUTPUT.TXT", "w");
    fprintf(fp, "%d\n", diff_best);
    for (i = 0; i < size; i++)
        fprintf(fp, "%d ", size - solution[i]);
    fclose(fp);
}

* 참고.
주어진 밭의 수확량에서 동생과 형의 차이를 1로 만드는 데에는 아래와 같은 방법들이 존재한다.

• 2 2 2 3 4 (문제의 예시)
  
• 1 2 2 3 4
• 0 0 3 5 5
  

물론 이 밖에도 있을 것이다. 내가 짠 위의 소스는 두번째 결과를 낸다.
강조한 줄이 하나 있는데, if 내의 <를 <=로 바꾸면 세번째 결과를 내게 된다.

코드에 대한 자세한 설명은 다음 기회로 미룬다.