2010 정보올림피아드 지역본선 고등부 문제 Review (3)

색상환

  색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다.

그림 1. 먼셀의 20색상환

  색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다.
  주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자.  먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있게 10개의 색을 선택하는 경우의 수는 2이지만, 시각적 대비 효과를 얻을 수 있게 11개 이상의 색을 선택할 수 없으므로 이 경우의 수는 0이다.
  주어진 정수 N과 K에 대하여, N개의 색으로 구성되어 있는 색상환 (N색상환)에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 프로그램을 작성하시오.
  프로그램 이름은 COLOR.EXE로 하고 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식
  입력 파일의 이름은 INPUT.TXT이다.  입력 파일의 첫째 줄에 색상환에 포함된 색의 개수를 나타내는 양의 정수 N(4≤N≤1,000)이 주어지고, 둘째 줄에 색상환에서 선택할 색의 개수 K(1≤K≤N)가 주어진다.

출력 형식
  출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다.

입력과 출력의 예
입력 (INPUT.TXT)

4
2

출력 (OUTPUT.TXT)

2

하향식 풀이를 요구하는 문제다. 물론 그 덕분에 동적 계획법으로 답을 낼 수도 있다.

우선 일반적인 경우에 대해 점화식을 얻기 위해 색상환을 선형으로 쪼개 보자.

색상환에서 하나를 고르면 이것은 선택된 K개 중 하나이거나, 선택되지 않은 (N-K)개 중 하나다.

따라서 위 그림과 같이 N색상환 중 K색을 고르는 경우의 수는 다음과 같이 정해진다.

circle(n, k) = stripe(n - 3, k - 1) + stripe(n - 1, k)

circle(a, b)는 a색상환에서, stripe(a, b)는 a색띠에서 b개 색을 인접하지 않게 고르는 경우의 수이다.

다음으로 색띠에 대한 점화식을 생각해 보자.

색띠의 마지막 색은 선택된 것이거나, 선택되지 않은 것이다.
따라서 다음과 같은 점화식을 얻는다.

stripe(n, k) = stripe(n - 1, k) + stripe(n - 2, k - 1)
stripe(n, 0) = 1, stripe(1, 1) = 1, stripe(1, k') = stripe(2, k') = 0 where k' > 1

n≤2k인 경우는 없다. 따라서 동적 계획법을 사용할 경우 테이블은 n 방향 우선으로 확장해 나간다.

#include <stdio.h>
#define D 1000000003

int main()
{
    int n, k;
    int i, j;
    int s[1000][500] = {{0}};
    FILE *fp;
    fp = fopen("INPUT.TXT", "r");
    fflush(stdout);
    fscanf(fp, "%d %d", &n, &k);
    fclose(fp);
    fopen("OUTPUT.TXT", "w");
    if (2 * k > n)
        fprintf(fp, "0");
    else
    {
        s[0][0] = s[1][0] = s[1][1] = 1;
        for (i = 2; i <= n; i++)
        {
            for (j = 0; j <= i / 2 + 3; j++)
            {
                if (j == 0)
                    s[i][j] = 1;
                else
                    s[i][j] = (s[i - 1][j] + s[i - 2][j - 1]) % D;
            }
        }
    }
    fprintf(fp, "%d", (s[n - 3][k - 1] + s[n - 1][k]) % D);
    fclose(fp);
    return 0;
}

저는 워낙 다이나믹 로동프로그래밍에 약해서 시험장에서 직접 n과 k에 대한 공식을 구해서 맞혔습니다.