단위분수 만들기

회사에서 일을 하다가 할 일이 없어서 며칠을 놀게 되었다. 그냥 놀고 있자니 눈치는 보이고 뭔가 일하는 것처럼 보이기 위해 이것저것 찾던중에 정보올림피아드란 걸 알게 되었다. 거기에 나온 문제들이나 한개씩 풀어봐야겠다 싶어서 시작하게 되었다.
그런데 생각보다 너무나 어려웠다. 처음에 1번 문제를 푸는데 하루 걸렸다. -_-;
이 글에 올리려고 하는 "단위분수 만들기"는 이틀 걸렸다. ㅡㅜ
어떻게 해야 할지 전혀 몰랐다가 1~9까지의 수를 한번씩 사용해 100이 되는 대분수를 만드는 법을 소스로 짠걸 보게 되었다. 그거에 많은 힌트를 얻어서 단위분수 만들기를 짤 수 있게 되었다. 어쨋거나 무지 어렵다. 나에겐... ㅡㅜ

문제) 1부터 9까지의 수를 한번씩 사용하여 1/2부터 1/9까지의 단위분수를 만드는 프로그램을 작성하라.

앞서 힌트가 되었던 100이 되는 대분수 만들기를 보면 분모나 분자들이 취할 수 있는 자리수가 몇가지로 정해져 있다는 것이다. 그처럼 이 단위분수 만들기도 분모와 분자의 자리수가 정해진다. 분자의 자리수는 4자리로 고정이다. 3자리 이하이거나 5자리 이상이면 절대로 단위분수가 나올 수 없는 조건이 된다.
1/2 = a/b 는 b(분모) = 2 * a(분자) 이라는 식이 성립시킨다. 분자가 3자리의 경우에 가장 큰수가 987이다. 그리고 가장 작은 분모의 값은 123456이 된다. 분자에 어떤 값을 곱해서 분모와 값이 같아야 하는데 가장 큰 9를 곱해도 8883밖에 되질 않는다. 그래서 3자리보단 더 큰 자리수여야 한다. 그럼 분자의 자리수가 5자리인 경우를 보자. 5자리의 분자의 값 중에 가장 작은 값이 12345이다. 그리고 분모의 값을 나머지 수로 만들 수 있는 가장 큰 9876으로 해보자. 분자의 값에 어떤 수(1~9)를 곱해서 분모가 되어야 하는데 가장 작은 1을 곱해도 분모보다 값이 크다. 그러므로 분자의 자리 수는 5자리보다 적어야 한다. 그럼 분자의 자리 수는 자연스럽게 4자리로 고정이 되버리고 그렇게 분모의 자리 수는 5자리가 된다.

void olym2()
{
    ofstream out;
    out.open("out_olym2.txt", ios::out | ios::trunc);
    // a * b = c
    // a는 1자리로 2~9까지 가능
    // b는 4자리로 분자에 해당
    // c는 5자리로 분모에 해당
    int a, b, c;
    char temp[9] = "";
    for(a=2; a<=9; a++)                 // 1자리로 a가 나타낼 수 있는 모든 수만큼 
    {
        for(b=1234; b<=9876; b++)       // 4자리로 b가(분자) 나타낼 수 있는 모든 수만큼
        {
            sprintf(temp, "%d", b);
            if(!check(temp))
                continue;
            c = a * b;                  // 분자(b)에 어떤 값(a)을 곱하면 분모(c)와 값이 같다.
            sprintf(temp, "%d%d", b, c);
            if(strlen(temp) != 9)       // 분자 분모의 자리수 합이 9가 안되는 경우는 제외
                continue;
            if(check(temp))
            {
                printf("1/%d = %d/%d\n", a, b, c);
                out << 1/a << " = " << b << "/" << c << "\n";
            }
        }
    }
}
int check(char* str)
{
    char check[11] = "0nnnnnnnnn";
    int x = atoi(str);
    int i=0;
   
    while(x>0)
    {
        i = x%10;

        if(check[i] == '0')             // 0이 있으면 제외
            return 0;
        else if(check[i] != 'n')        // 중복인 수가 있으면 제외
            return 0;
        else
            check[i] = 'y';             // 중복이 아니면 체크
        x = x/10;
    }
    return 1; 
}