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

복불복

  1박2일 제작진은 다음과 같은 새로운 복불복 게임을 제안하였다. 먼저 게임을 하는 한 사람에게 K개의 조약돌을 주고, 숫자가 적혀있는 회전판을 N번 돌리게 한다. 게임을 하는 사람은 회전판을 돌려서 나오는 숫자만큼의 조약돌을 제작진에게 되돌려 주어야 한다. 회전판을 N번 돌리는 동안 제작진에게 줄 수 있는 조약돌이 있으면 게임을 하는 사람이 이기게 되고, 제작진에게 주어야 하는 조약돌이 모자라게 되면 게임에서 지게 된다.
  회전판에는 T개의 숫자가 그려지고, 그려지는 숫자는 0 이상 T-1 이하의 정수 중 하나이다. 회전판에 사용되는 정수는 중복 사용이 가능하고, 0부터 T-1 사이의 정수 모두가 다 회전판에 나타나야 하는 것은 아니다.
  N과 K, 그리고 T와 회전판에 그려진 모든 숫자가 주어질 때, 게임을 하는 사람이 이길 수 있는 경우의 수를 계산하는 프로그램을 작성하라.
단, 회전판에 같은 수가 여러 개 있을 때 이들 수는 값은 같지만 서로 다른 경우의 수들로 계산된다.
  예를 들어, 6개의 숫자 0, 1, 1, 2, 4, 5가 그려진 회전판에서 가지고 있는 조약돌의 수가 6개이고, 회전판을 2번 돌린다면, 게임을 하는 사람이 이길 수 있는 경우의 수는 30이다. 즉, 처음 나온 정수가 0 혹은 1이면, 그 다음에 어떤 수가 나오더라도 게임을 이길 수 있으며, 2가 처음 나오는 경우에는 정수 5가 나오는 경우를 제외한 5가지 경우가 존재한다. 4가 처음 나오는 경우는 4가지 경우, 5가 처음 나오는 경우에는 3가지 경우가 존재하게 된다.
  실행파일의 이름은 LUCK.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식
  입력 파일의 이름은 INPUT.TXT로 한다. 첫째 줄에 3개의 정수 N, K, T가 빈칸을 사이에 두고 주어진다. N은 회전판을 돌리는 횟수를 나타내고, K는 게임을 하는 사람에게 처음 주어지는 조약돌의 개수를 나타낸다. T는 회전판에 그려져 있는 정수들의 수이다. N은 1 이상 100,000 이하이고, K는 1 이상 1,000 이하, T는 2 이상 20,000 이하이다. 둘째 줄부터 T개의 줄에는 각 줄마다 회전판에 적혀져 있는 정수가 주어진다.

출력 형식
  출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄에 게임을 하는 사람이 이길 수 있는 경우의 수를 42,043으로 나눈 나머지 값으로 출력한다.

입력과 출력의 예

입력 (INPUT.TXT)

2 6 6
0
1
1
2
4
5

출력 (OUTPUT.TXT)

30

모든 잡소리를 집어치우고 가장 간단한 해법부터 알아보자.

K개의 조약돌을 갖고 회전판을 N번 돌렸을 경우 이길 수 있는 경우의 수를 어떻게 구할까?
이것이 문제의 요지이다.

실제로 게임의 흐름을 따라가 보면 이런 식이다.

회전판에 0이 나왔다 -> 앞으로 K개의 조약돌을 가지고 회전판을 (N-1)번 돌려!
회전판에 1이 나왔다 -> 앞으로 (K-1)개의 조약돌을 가지고 회전판을 (N-1)번 돌려!
회전판에 2가 나왔다 -> 앞으로 (K-2)개의 조약돌을 가지고 회전판을 (N-1)번 돌려!
...

보라. 점화식이 완성되었다.

실제로 문제를 해결할 때 0, 1, 1, 2, 4, 5가 주어지면,
{0, 1, 1, 2, 4, 5}로 넣고 각각의 회전판 숫자에 대해 호출하는 것보다
{1, 2, 1, 0, 1, 1}로 넣어서 인덱스를 회전판 숫자로 놓고 각각의 경우에 곱셈을 해 주는 것이 빠르다.
직전에 계산한 것와 k를 비교해 보고 같으면 그대로 더해 주는 방법도 있지만,
문제에는 회전판 숫자를 작은 것부터 준다는 조건이 없었으므로 낭패 볼 수 있다.

이에 따라 일단 함수를 이렇게 나누고 main()을 정리한다.

#include <stdio.h>

int n, k, t;
int nums[20000] = {0, };
int casewin;

void readfile();
int luck(int turns, int rest);
void writefile();

int main()
{
    readfile();
    casewin = luck(n, k);
    writefile();
    return 0;
}

계획대로 진행하기 위해 readfile()에서는 파일을 읽어 전역변수 n, k, t와 nums[]를 채운다.
luck(int, int)에서는 위의 점화식과 조건에 따라 회전판 결과를 증가시켜 가며 경우의 수를 센다.
writefile()에서는 계산 결과를 파일에 기록한다.

결국 소스는 이렇게 나온다.

#include <stdio.h>

int n, k, t;
int nums[20000] = {0, };
int casewin;

void readfile();
int luck(int turns, int rest);
void writefile();

int main()
{
    readfile();
    casewin = luck(n, k);
    writefile();
    return 0;
}

void readfile()
{
    FILE *fp;
    int i, piece;
    fp = fopen("INPUT.TXT", "r");
    fscanf(fp, "%d %d %d", &n, &k, &t);
    for (i = 0; i < t; i++)
    {
        fscanf(fp, "%d", &piece);
        nums[piece]++;
    }
    fclose(fp);
}

int luck(int turns, int rest)
{
    int i, sum = 0;
    if (turns == 0)
    {
        return 1;
    }
    else
    {
        for (i = 0; i < t; i++)
            if (nums[i] != 0 && i <= rest)
                sum += luck(turns - 1, rest - i) * nums[i];
        return sum % 42043;
    }
}

void writefile()
{
    FILE *fp;
    fp = fopen("OUTPUT.TXT", "w");
    fprintf(fp, "%d", casewin);
    fclose(fp);
}

시험 당일이 아니라 그런지 정말 쉽다. 왜...ㅜㅠ