이 블로그는 방문자 통계를 위해 티스토리 기본 기능과 Woopra를 사용합니다. 원하지 않으신다면 사용하시는 웹 브라우저에 내장된 DNT 헤더를 켜고, JavaScript를 끄셔도 무방합니다.
이 블로그 방문자의 약 60%는 네이버 검색을 사용하십니다. 을 이용하시면 더 유용한 정보를 쉽게 얻게 되실 수도 있습니다. [mediatoday]
« 2019/11 »
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
블로그 이미지
제가 주제인 블로그... 그냥 주제 없는 블로그입니다. 전공 분야나 예전 관심 분야 등등에 관한 글이 우선입니다만, 두어 문단을 넘길 만한 글이라면 대강 정리해 기록합니다. 학부생입니다. 트위터에서 볼 수 있습니다. http://aurynj.net/ 어­리


색상환

  색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(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에 대한 공식을 구해서 맞혔습니다.

댓글을 달아 주세요

  1. ALoz 2011.05.10 17:01 신고  댓글주소  수정/삭제  댓글쓰기

    하향식 풀이가 뭔지 설명해 주실 수 있나요?

    • 어­리 2011.05.17 01:30 신고  댓글주소  수정/삭제

      컴퓨터 알고리즘에서 하향식과 상향식 풀이로 구분되는 것은 많지만 그 중 점화식으로 구성되는 솔루션에 대해 말하자면, 점화식의 마지막 항을 구할 항으로 놓았을 때, 큰 항으로부터 이전에 구해야 할 항들을 정해 base case까지 내려가는 방법을 하향식이라고 하고, 반대로 base case에서 출발해 작은 항으로부터 큰 항을 계산해 나가면서 구할 항에 도달하는 방법을 상향식이라고 합니다.

    • ALoz 2011.05.17 23:17 신고  댓글주소  수정/삭제

      감사합니다 ㅎ

  2. 지나가는인간 2011.05.16 22:20  댓글주소  수정/삭제  댓글쓰기

    저기요 님이푼것에대해 말하지만요 문제가 있네요 k가 n이거나 n-1일경우에는 n을출력해야되는데요 n을출력하지못하는군요.

    • 어­리 2011.05.17 01:33 신고  댓글주소  수정/삭제

      무슨 말씀이시죠? N개의 색상환에서 아무 둘도 인접하지 않는 N개의 색을 고를 수는 없는데요... 혹시 제가 문제를 잘못 이해했나요?

  3. 1young 2011.05.19 17:45  댓글주소  수정/삭제  댓글쓰기

    stripe(2,1)은 1이 되어야 하는 것 아닌가요?
    2색띠에서 1가지 색을 인접하지않게 고르는 건 2가지라고 생각되서요....

    • 어­리 2011.05.21 12:00 신고  댓글주소  수정/삭제

      오타였습니다. 소스에서 보시다시피 stripe(1, 0) = stripe(1, 1) = 1이고, stripe(2, 1)은 2입니다. 정확한 지적 감사합니다. 수정합니다^^