이 블로그는 방문자 통계를 위해 티스토리 기본 기능과 Woopra를 사용합니다. 원하지 않으신다면 사용하시는 웹 브라우저에 내장된 DNT 헤더를 켜고, JavaScript를 끄셔도 무방합니다.
이 블로그 방문자의 약 60%는 네이버 검색을 사용하십니다. 을 이용하시면 더 유용한 정보를 쉽게 얻게 되실 수도 있습니다. [mediatoday]
« 2018/07 »
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 31        
블로그 이미지
제가 주제인 블로그... 그냥 주제 없는 블로그입니다. 전공 분야나 예전 관심 분야 등등에 관한 글이 우선입니다만, 두어 문단을 넘길 만한 글이라면 대강 정리해 기록합니다. 학부생입니다. 트위터에서 볼 수 있습니다. 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에 대한 공식을 구해서 맞혔습니다.
가로수

  직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.
   편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.
   예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.
  심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.
   실행파일의 이름은 TREE.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식
   입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3≤N≤100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 100,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르다.

출력 형식
   출력 파일의 이름은 OUTPUT.TXT이다. 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

입력과 출력의 예 (1)
입력 (INPUT.TXT)
4
1
3
7
13
출력 (OUTPUT.TXT)
3

입력과 출력의 예 (2)
입력 (INPUT.TXT)
4
2
6
12
18
출력 (OUTPUT.TXT)
5
인접한 가로수들의 간격의 최대공약수를 구해야 하는 문제이다.
가장 기본적인 풀이를 생각하자면, 우선 가로수의 위치를 모두 받고(int position[100000]), 간격을 계산하고(int delta[100000]), 최대공약수를 계산한다. 그리고 간격을 각각 최대공약수로 나눠 더한다.
#include <stdio.h>
int gcd(int a, int b)
{
    int t;
    if (a < b) t = a, a = b, b = t;
    if (a % b == 0)
        return b;
    else
        return gcd(b, a % b);
}
int main()
{
    int i, n;
    int position[100000], delta[100000];
    int g, t = 0;
    FILE *fp;
    fp = fopen("INPUT.TXT", "r");
    fflush(stdout);
    fscanf(fp, "%d", &n);
    for (i = 0; i < n; i++)
    {
        fflush(stdout);
        fscanf(fp, "%d", &position[i]);
    }
    fclose(fp);
    for (i = n - 1; i >= 0; i--)
    {
        delta[i] = position[i + 1] - position[i];
    }
    g = delta[0];
    for (i = 1; i < n - 1; i++)
    {
        g = gcd(delta[i], g);
    }
    for (i = 0; i < n - 1; i++)
    {
        t += delta[i] / g - 1;
    }
    fp = fopen("OUTPUT.TXT", "w");
    fprintf(fp, "%d", t);
    fclose(fp);
    return 0;
}

그러나 메모리와 시간을 아끼자면 몇 가지 대안 풀이를 생각할 수 있다. 일단 간격을 계산하고 나면 위치가 쓸모없어지므로 위치를 받을 때부터 간격을 계산하며, 위치를 저장하지 않는다.
#include <stdio.h>

int gcd(int a, int b)
{
    int t;
    if (a < b) t = a, a = b, b = t;
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
int main()
{
    int a, b = 0;
    int g = 0, t = 0;
    int q[99999];
    int i, n;
    FILE *fp;
    fp = fopen("INPUT.TXT", "r");
    fflush(stdout);
    fscanf(fp, "%d", &n);
    for (i = 0; i < n; i++)
    {
        a = b;
        fflush(stdout);
        fscanf(fp, "%d", &b);
        if (i == 0) continue;
        q[i] = b - a;
        g = gcd(b - a, g);
    }
    for (i = 1; i < n; i++)
        t += q[i] / g - 1;
    fclose(fp);
    fp = fopen("OUTPUT.TXT", "w");
    fprintf(fp, "%d", t);
    fclose(fp);
    return 0;
}

참고로 이 문제에는 가로수의 위치가 오름차순으로 제시된다는 조건이 없다. 따라서 위치를 모두 받고 이를 정렬해 준 후에 간격을 계산하는 것이 맞다. (단, 간격을 위치 배열에 저장해서 메모리를 절약할 수 있다.) 그러나 테스트 데이터는 모두 오름차순으로 제시되어 있었다고 한다. 나는 만약을 생각해 정렬했지만, 문제를 쓰면서 오름차순을 명시하는 걸 빼먹은 모양이다.
블로그에 떡밥이 없어서 1년이 거의 다 된 소재를 지금이라도 뿌리기로 했다.
이렇게라도 활동을 시작하면 뭔가 소재가 생각나지 않을까... (도망)

주사위 네개

1에서부터 6까지의 눈을 가진 4개의 주사위를 던져서 다음과 같은 규칙에 따라 상금을 받는 게임이 있다.

규칙(1) 같은 눈이 4개가 나오면 50,000원+(같은 눈)*5,000원의 상금을 받게 된다.

규칙(2) 같은 눈이 3개만 나오면 10,000원+(3개가 나온 눈)*1,000원의 상금을 받게 된다.

규칙(3) 같은 눈이 2개씩 두 쌍이 나오는 경우에는 2,000원+(2개가 나온 눈)*500원+(또 다른 2개가 나온 눈)*500원의 상금을 받게 된다.

규칙(4) 같은 눈이 2개만 나오는 경우에는 1,000원+(같은 눈)*100원의 상금을 받게 된다.

규칙(5) 모두 다른 눈이 나오는 경우에는 (그 중 가장 큰 눈)*100원의 상금을 받게 된다.

  예를 들어, 4개의 눈이 3, 3, 3, 3으로 주어지면 50,000+3*5,000으로 계산되어 65,000원의 상금을 받게 된다. 4개의 눈이 3, 3, 6, 3으로 주어지면 상금은 10,000+3*1,000으로 계산되어 13,000원을 받게 된다. 또 4개의 눈이 2, 2, 6, 6으로 주어지면 2,000+2*500+6*500으로 계산되어 6,000원을 받게 된다. 4개의 눈이 6, 2, 1, 6으로 주어지면 1,000+6*100으로 계산되어 1,600원을 받게 된다. 4개의 눈이 6, 2, 1, 5로 주어지면 그 중 가장 큰 값이 6이므로 6*100으로 계산되어 600원을 상금으로 받게 된다.
   N(1≤N≤1,000)명이 주사위 게임에 참여하였을 때, 가장 많은 상금을 받은 사람의 상금을 출력하는 프로그램을 작성하시오.
   실행파일의 이름은 DICE4.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식
   입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에는 참여하는 사람 수 N이 주어지고 그 다음 줄부터 N개의 줄에 사람들이 주사위를 던진 4개의 눈이 빈칸을 사이에 두고 각각 주어진다.

출력 형식
   출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 가장 많은 상금을 받은 사람의 상금을 출력한다.

입력과 출력의 예

입력(INPUT.TXT)
4
3 3 3 3
3 3 6 3
2 2 6 6
6 2 1 5
출력(OUTPUT.TXT)
65000
맞춤법에 의하면 '주사위 네 개'입니다. 관형어와 체언은 떼어 씁니다. 맞춤법 틀리는 정올

간단한 다중 조건식으로 해결할 수 있다.
#include <stdio.h>

int main()
{
    int n;
    int a, b, c, d;
    int pt, pt_max = 0;
    FILE *fp;
    fp = fopen("INPUT.TXT", "r");
    fflush(stdout);
    fscanf(fp, "%d", &n);
    while (n-- > 0) {
        fflush(stdout);
        fscanf(fp, "%d %d %d %d", &a, &b, &c, &d);
        if (a == b && b == c && c == d)
            pt = 50000 + a * 5000;
        else if ((a == b && b == c) || (a == b && b == d) || (a == c && c == d))
            pt = 10000 + a * 1000;
        else if ((a == b && c == d) || (a == c && b == d))
            pt = 2000 + a * 500 + d * 500;
        else if (a == d && b == c)
            pt = 2000 + a * 500 + b * 500;
        else if (a == b || a == c || a == d)
            pt = 1000 + a * 100;
        else if (b == c || b == d)
            pt = 1000 + b * 100;
        else if (c == d)
            pt = 1000 + c * 100;
        else if (a > b && a > c && a > d)
            pt = a * 100;
        else if (b > c && b > d)
            pt = b * 100;
        else if (c > d)
            pt = c * 100;
        else
            pt = d * 100;
        if (pt > pt_max) pt_max = pt;
    }
    fclose(fp);
    fp = fopen("OUTPUT.TXT", "w");
    fprintf(fp, "%d", pt_max);
    fclose(fp);
    return 0;
}

나는 당시에 시험장에서 조건문 분기 중복을 없애려다 1시간을 버렸다.
시험 당일에 5개의 문제 중 5번을 가장 쉽게 푼 것 같다.
중앙문자열

  문자열에서 교체 연산은 문자열의 한 문자를 다른 문자로 바꾸는 연산이다. 예를 들어, 문자열 “computer”에서 4번째 문자 p를 m으로 교체하면 “commuter”가 된다.
  같은 길이의 두 문자열 P와 Q의 거리 d(P,Q)는 P를 Q로 바꾸기 위한 교체 연산의 최소 개수로 정의된다. 예를 들어 P = “computers”, Q = “consumers”라 하면, P에서 3번째 문자 m을 n으로, 4번째 문자 p를 s로, 6번째 문자 t를 m으로 바꾸면 Q가 된다. 따라서 P와 Q 사이의 거리는 3이다.
  A, B, C를 같은 길이의 문자열이라 하자. 이 때 어떤 문자열 W의 반경 r(W)는 문자열 W와 문자열 A, B, C와의 거리 중 최대값으로 정의된다. 즉, r(W)= max{ d(W,A), d(W,B), d(W,C) } 이다. 예를 들어, A = “computers”, B = “consumers”, C = “consensus”일 때, X = “consunsrs”라 두면, A, B, C와 X 사이의 거리는 d(X,A) = 4, d(X,B) = 2, d(X,C) = 2이므로, X의 반경 r(X)는 4이다.
  문자열 A, B, C의 중앙문자열은 A, B, C와의 반경이 최소가 되는 문자열로 정의된다. 예를 들어, 문자열 A, B, C가 위와 같이 주어졌을 때, Y = “consuners”라 두면, Y의 반경은 3이고, 반경이 2인 문자열은 존재하지 않으므로, Y는 A, B, C의 중앙문자열이 된다.
  영어 소문자들로만 구성된 문자열 A, B, C가 주어졌을 때, 이들의 중앙문자열을 구하는 프로그램을 작성하라.
  실행파일의 이름은 CSTRING.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식
  입력 파일의 이름은 INPUT.TXT로 한다. 첫 째 줄에는 문자열 A가 주어진다. 마찬가지로 문자열 B와 C가 각각 둘째 줄과 셋째 줄에 주어진다. 세 문자열의 길이는 동일하고, 그 길이는 1 이상 100,000 이하이다.

출력 형식
  출력 파일의 이름은 OUTPUT.TXT로 한다. 첫 째 줄에 중앙문자열의 반경을 출력하고 둘째 줄에 중앙문자열을 출력한다. 중앙문자열이 여러 개인 경우 하나만 출력한다.

입력과 출력의 예

입력 (INPUT.TXT)
computers
consumers
consensus
출력 (OUTPUT.TXT)
3
consuners
왜 이번에는 그 해법을 잊어버린 것인가... 하고 생각해 보니 예시답안은 맞았지만,
커팅 없이 DFS로 풀었기 때문에 100000글자 테스트에서 1초를 넘겼을 것이라고 짐작했던 기억이 난다.

참고: 위의 조건 computers, consumers, consensus에,
r = 3이 되는 중앙 문자열은 여러 가지가 있다.
  • comsuneus
  • comsunsrs
  • comseners
  • conpuneus
  • conpunsrs
  • conpeners
  • consuteus
  • consutsrs
  • consuners
  • conseters
이 중 하나를 답으로 낸다면 코드는 정상이다.


당시에 제출했던 코드는 약간 더 최적화가 되어 있지만,
실제 재귀 호출을 이용해 커팅 없는 DFS로 풀면 소스 코드가 어떻게 되나 보자.
시간 복잡도는 3^n이다.
#include <stdio.h>
#include <string.h>
#define MAX(X, Y) (X > Y ? (X) : (Y))

char inputs[3][100001];
char datis[100001];
char optis[100001];
int optii;
int ilen;

void readfile();
void makecstr(int i);
int r(char *w, int len);
int d(char *w, int len, int i);
void writefile();

int main()
{
    readfile();
    makecstr(0);
    writefile();
    return 0;
}

void readfile()
{
    int i;
    FILE* fp;
    fp = fopen("INPUT.TXT", "r");
    for (i = 0; i < 3; i++)
        fscanf(fp, "%s", inputs[i]);
    fclose(fp);
    ilen = strlen(inputs[0]);
    optii = ilen;
}

void makecstr(int i)
{
    if (i < ilen)
    {
        datis[i] = inputs[0][i];
        makecstr(i + 1);
        datis[i] = inputs[1][i];
        makecstr(i + 1);
        datis[i] = inputs[2][i];
        makecstr(i + 1);
    }
    else
    {
        if (r(datis, ilen) < optii)
        {
            strcpy(optis, datis);
            optii = r(datis, ilen);
        }
    }
}

int r(char *w, int len)
{
    return MAX(MAX(d(w, len, 0),d(w, len, 1)),d(w, len, 2));
}

int d(char *w, int len, int i)
{
    int j, c = 0;
    for (j = 0; j < len; j++)
        if (w[j] != inputs[i][j])
            c++;
    return c;
}

void writefile()
{
    FILE* fp;
    fp = fopen("OUTPUT.TXT", "w");
    fprintf(fp, "%d\n%s", optii, optis);
    fclose(fp);
}
3^n이라니.

이 대참사는 문자열을 앞에서부터 완성했기 때문에 벌어진다.
이렇게 푼다면 커팅을 한다 해도 선형시간을 만들 수 없다. 워스트 케이스 때문에...

심사위원들이 컴퓨터를 보고 당황했을 거다.
짧은 문자열에서 답을 내는 프로그램에 긴 문자열을 돌렸더니 거의 멎었을테니.


결론적으로 제대로 풀기 위해서는 DFS를 쓰면 안 된다.
세 문자열에서 같은 자리에 있는 문자들의 관계를 보고 필요한 만큼만 시도해야 하는 것이다.

이 때 세가지 경우가 존재하고 각각에 원칙이 따른다.
  1. xxx의 경우. 이 때 최적해에서 이 자리는 무조건 x이다.
  2. xxy / xyx / yxx의 경우. 이 때 최적해에서 이 자리는 x가 유리하다.
  3. xyz의 경우. 위의 원칙에 따라 만든 후 r이 작아지도록 조정한다.
    r이 충분히 작아지지 않으면 2에서 y를 고를 수 있다.
얼핏 보기에는 너무 직관적이어서 코딩하기에는 적절하지 못한 아이디어이다.
하지만 사실 상당히 greedy한 기법이며, 선형 시간 안에 해결 가능하다.
이에 따라 코딩하면 아래와 같이 된다.
#include <stdio.h>
#include <string.h>
#define MAX(X, Y) (X > Y ? (X) : (Y))
#define MIN(X, Y) (X < Y ? (X) : (Y))
#define MAX3(X, Y, Z) MAX(X, MAX(Y, Z))
#define MIN3(X, Y, Z) MIN(X, MIN(Y, Z))

char inputs[3][100001];
char optis[100001];
int ilen;
int d0 = 0, d1 = 0, d2 = 0;

void readfile();
void makecstr();
void writefile();

int main()
{
    readfile();
    makecstr();
    writefile();
    return 0;
}

void readfile()
{
    int i;
    FILE* fp;
    fp = fopen("INPUT.TXT", "r");
    for (i = 0; i < 3; i++)
        fscanf(fp, "%s", &inputs[i]);
    fclose(fp);
    ilen = strlen(inputs[0]);
}

void makecstr()
{
    for (i = 0; i < ilen; i++)
    {
        if (inputs[0][i] == inputs[1][i] &&
            inputs[1][i] == inputs[2][i])
        {
            optis[i] = inputs[0][i];
        }
        else if (inputs[1][i] == inputs[2][i] &&
            inputs[1][i] != inputs[0][i])
        {
            optis[i] = inputs[1][i];
            d0++;
        }
        else if (inputs[2][i] == inputs[0][i] &&
            inputs[2][i] != inputs[1][i])
        {
            optis[i] = inputs[2][i];
            d1++;
        }
        else if (inputs[0][i] == inputs[1][i] &&
            inputs[0][i] != inputs[2][i])
        {
            optis[i] = inputs[0][i];
            d2++;
        }
    }

    for (i = 0; i < ilen; i++)
    {
        if (inputs[0][i] != inputs[1][i] &&
            inputs[1][i] != inputs[2][i] &&
            inputs[2][i] != inputs[0][i])
        {
            if (d2 == MAX3(d0, d1, d2))
            {
                optis[i] = inputs[2][i];
                d0++; d1++;
            }
            else if (d1 == MAX3(d0, d1, d2))
            {
                optis[i] = inputs[1][i];
                d2++; d0++;
            }
            else 
            {
                optis[i] = inputs[0][i];
                d1++; d2++;
            }
        }
    }

    for (i = 0; i < ilen; i++)
    {
        if (MAX3(d0, d1, d2) - MIN3(d0, d1, d2) < 2)
            break;

        if (d0 == MAX3(d0, d1, d2) &&
            inputs[1][i] == inputs[2][i] &&
            inputs[1][i] != inputs[0][i])
        {
            optis[i] = inputs[0][i];
            d1++; d2++; d0--;
        }
        else if (d1 == MAX3(d0, d1, d2) &&
            inputs[2][i] == inputs[0][i] &&
            inputs[2][i] != inputs[1][i])
        {
            optis[i] = inputs[1][i];
            d2++; d0++; d1--;
        }
        else if (d2 == MAX3(d0, d1, d2) &&
            inputs[0][i] == inputs[1][i] &&
            inputs[0][i] != inputs[2][i])
        {
            optis[i] = inputs[2][i];
            d0++; d1++; d2--;
        }
    }
}

void writefile()
{
    FILE* fp;
    fp = fopen("OUTPUT.TXT", "w");
    fprintf(fp, "%d\n%s", MAX3(d0, d1, d2), optis);
    fclose(fp);
}

makecstr() 안에 있는 3개의 for 루프 속 if-else if 순서를 서로 바꿔도 무방하다.
이에 따라 output.txt 안의 답안이 달라질 수 있다.

여기까지.
복불복

  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);
}

시험 당일이 아니라 그런지 정말 쉽다. 왜...ㅜㅠ
이 포스트에서는 지난번에 올린 소스 코드가 어떤 식으로 구성되었는지 설명해 보겠다.
(참 빨리 올린다...=_=;)

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

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



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

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

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


너무 늦게.
지난번에 문제를 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 내의 <를 <=로 바꾸면 세번째 결과를 내게 된다.

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

3번 문제는 처음 보고 정체를 알 수 없었다.

의좋은 형제

  어떤 N × N 개의 단위 구역으로 구성된 논이 있다. 각 단위 구역에서는 쌀이 생산되는데 구역에 따라서 쌀의 생산량이 다르다. 아래는 5 × 5 = 25개의 단위 구역으로 나누어진 논을 보여주고 있다. 각 구역에 적혀 있는 숫자는 예상되는 쌀의 수확량(가마)이다.

3
4
5
1
8
8
2
3
2
2
0
2
9
5
4
1
11
3
0
5
4
5
2
7
1

  두 의좋은 형제는 이 N × N의 논을 다음과 같이 두 부분으로 나누어 형은 아래쪽에 있는 땅을 가지고, 동생은 위쪽의 땅을 가지기로 하였다. 전체 구역을 마구잡이로 나누면 기계로 농사를 짓는데 불편하기 때문에 각 형제에게 배분된 구역이 단조 증가하는 계단 모양이 되게 하려고 한다. 즉, 주어진 논을 N × N 행렬로 볼 때 형이 특정 열에서 할당받는 구역의 개수는 바로 왼쪽 열에서 받은 구역의 개수보다 크거나 같아야 한다. 예를 들어 다음 세 그림 중 그림 1과 2는 올바른 배정 방법으로, 회색 지역은 형의 논, 나머지 부분은 동생의 논이다. 그러나 그림 3은 논을 나누는 규칙을 어기는 경우이다.
  두 형제는 논을 공평하게 나누기 위해, 위와 같은 방법들 중 각 영역의 예상 수확량의 차이가 되도록 적게 하고자 한다. 예를 들어 그림 1은 형의 예상 수확량이 48, 동생이 49로 최적인 경우이나, 그림 2는 형은 39, 동생은 58로 공평하게 나눠지지 않은 경우이다. 주어진 논을 최대한 공평하게 나누는 방법을 구하는 프로그램을 작성하라.
  실행 파일의 이름은 BRO.EXE로 한다. 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.
 
3
4
5
1
8
8
2
3
2
2
0
2
9
5
4
1
11
3
0
5
4
5
2
7
1
그림 1

3
4
5
1
8
8
2
3
2
2
0
2
9
5
4
1
11
3
0
5
4
5
2
7
1
그림 2

3
4
5
1
8
8
2
3
2
2
0
2
9
5
4
1
11
3
0
5
4
5
2
7
1
그림 3

입력 형식
  입력 파일의 이름은 INPUT.TXT로 한다. 첫째 줄에 논의 크기를 나타내는 정수 N (2≤N≤20)이 주어진다. 둘째 줄부터 N+1번째 줄에는 각 단위 구역의 예상 수확량이 0에서 100 사이의 정수로 주어진다. 둘째 줄에는 논의 제 1행의 각 구역의 예상 수확량에 해당하는 N개의 정수가 빈칸을 사이에 두고 주어지며, 셋째 줄에는 제 2행의 각 구역의 예상 수확량에 해당하는 N개의 정수가 빈 칸을 사이에 두고 주어진다. 넷째 줄부터 N+1번째 줄도 같은 형식으로 각 줄마다 N개 정수들이 주어진다.

출력 형식
  출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄에는 최적의 방법으로 영역을 나누었을 때의 예상 수확량 차이를 나타내는 정수를 출력하고, 둘째 줄에는 이 최적의 방법에서 논의 첫 번째 열부터 N번째 열까지 형이 배분받는 구역의 수를 나타내는 N개의 정수를 빈칸을 사이에 두고 출력한다. 방법이 여러 개인 경우 하나만 출력한다.

입력과 출력의 예

입력 (INPUT.TXT)
5
3 4 5 1 8
8 2 3 2 2
0 2 9 5 4
1 11 3 0 5
4 5 2 7 1
출력 (OUTPUT.TXT)
1
2 2 2 3 3

3번에서 드디어 알고리즘(?=알고리듬)을 짜야 하는 문제가 출현했다.


이 문제에서 n*n 구역으로 된 정사각형 논을 둘로 나눌 조건은 두 가지이다.
1. 왼쪽에서 오른쪽으로 올라가는 계단형으로 나눌 것.
2. 나뉜 두 부분에서 예상 수확량이 가장 비슷하게 (같을 수 있다면 같게) 할 것.


그래서 난 이런 식으로 프로그램을 짜기로 했다.

1) 논의 최대 크기는 20*20이고 예상 수확량은 음이 아닌 100 이하 정수이다.

int size, i, j;
char table[20][20]; //메모리를 아껴 보자는 심산


2) 모조리 입력받자. 총합의 절반에 가깝게 분할해야 하니 총합도 구하자.

int sect, total = 0;
FILE *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;
    }

3) 문제는 아래쪽을 기준으로 설명하고 있으나, 위에서 나누든 밑에서 나누든 결과는 같다.

차이는: 위쪽에서 볼 때 인접한 왼쪽 줄은 항상 오른쪽 줄보다 크거나 같아야 한다는...(;;)

그 대신 밑에서 새는 것보다 계산이 훨씬 수월하다.

왼쪽 줄을 1부터 늘리면서, 각 줄은 인접한 왼쪽 줄보다 작거나 같은 동안 늘리는 것이다.

그렇게 선택된 위쪽 구역의 넓이를 계산한다.

그런데 매 줄마다 수행해야 하는 문제는? -> 함수로 분해해서 스택을 사용하자.

그리고 각 함수는 절반을 넘어가는 순간 중단하고 최선의 상태 기억.



이 문제를 대회에서 직접 풀지는 못했지만 나름대로 솔루션을 제시해 봤다.

자세한 소스는 다음에...
이번 솔루션은 다소 간단하다.
또한 내가 작년에 쓰다가 한 문제를 망치게 만든 바로 그 방법이기도 하다....
(당시 int 형 변수를 제곱한 만큼 신규 할당시켰더니 오버플로)

바뀐 줄은 강조해 놓았다.
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, i, j;
    int higher = 0;
    int *tower = (int *)malloc(sizeof(int)*500001);
    FILE *fpi, *fpo;

    tower[0] = 100000000;
    fpi = fopen("INPUT.TXT", "r");
    fpo = fopen("OUTPUT.TXT", "w");
    fscanf(fpi, "%d", &n);

    for (i = 0; i < n; i++)
    {
        fscanf(fpi, "%d", tower + i);
        for (j = 0; j < i; j++)
        {
            if (tower[j] >= tower[i])
                higher = j + 1;
        }
        if (i != 0) fprintf(fpo, " ");
        fprintf(fpo, "%d", higher);
    }
    fclose(fpi);
    fclose(fpo);

    return 0;
}
.....;;

이 해법이 먹히는 까닭은 간단하다.

C 컴파일러는 함수, 블럭 맨 앞에 있는 변수들을 처음에 미리 설정해 놓는다.
이들은 운영체제 상에서 하나의 함수로 취급되어, 그 정보는 스택(stack)에 저장된다.
(시스템 콜/인터럽트 후에 적절한 작업 후 call, ret가 일어나기 때문이다.)

그러나 위와 같이 해 놓으면, *tower만 스택에 저장되고,
나머지는 (heap)에 저장된다. 힙은 포인터를 이용해 얼마든지[?] 확장할 수 있는 구조체이다.


고로 Stack Overflow가 일어나지 않는다.


지난번 글에 비해 이번 글은 상당히 늦었습니다. 시험 기간이라든지 등등...
일단 첫 번째 해법.

새로 입력받아서 비교한다!

어차피 입력받으면서 비교한 결과 출력하고 있으니까.
#include <stdio.h>

int main()
{
    int n, i, j;
    int tower, comp;
    int higher;
    FILE *fpi, *fpc, *fpo;

    fpi = fopen("INPUT.TXT", "r");
    fpo = fopen("OUTPUT.TXT", "w");
    fscanf(fpi, "%d", &n);

    for (i = 0; i < n; i++)
    {
        higher = 0;
        fscanf(fpi, "%d", &tower);
        fpc = fopen("INPUT.TXT", "r");
        for (j = 0; j < i; j++)
        {
            fscanf(fpc, "%d", &comp);
            if (comp >= tower)
                higher = j + 1;
        }
        if (i != 0) fprintf(fpo, " ");
        fprintf(fpo, "%d", higher);
    }
    fclose(fpi);
    fclose(fpo);

    return 0;
}

정상 작동.



뭐 이로써 크게 달라진 건 없습니다만...

C 콘솔에서 한번에 파일을 세 개 이상 열면 종종 에러를 맞는다는 소문이 있습니다.


게다가 파일을 계속 새로 읽어 오고 있으니,

시간제한 1초에 걸릴 가능성이 상당히 높군요.


다음 글에서 두 번째 해법을 들고 돌아오겠습니다.