프로젝트 오일러 #33 : 약분하는 추가 숫자

#33의 난이도는 5%네요.  쉬운 등급으로 설정된 문제입니다.

 

Project Euler #33 문제는 “Digit Cancelling Fractions”에 관한 내용입니다. 이 문제는 분모와 분자가 두 자리 수인 분수 중에서 특별한 조건을 만족하는 분수를 찾는 것입니다. 조건은 분자와 분모에 같은 숫자가 있을 때, 그 숫자를 단순히 “지우는” 방식으로 만든 새로운 분수가 원래 분수와 값이 같아야 한다는 것입니다.

예를 들어, 분수  \(\frac{49}{98}\) 은 특별한 분수입니다. 이 분수에서 분자와 분모의 9를 지우면  \(\frac{4}{8}\) 이 됩니다. 두 분수  \(\frac{49}{98}\) 과  \(\frac{4}{8}\) 은 서로 값이 같으므로 조건을 만족합니다. 그러나, 이 문제에서 이러한 방식은 분수를 단순히 축약하는 정상적인 방법(유클리드 호제법 등)과는 다르며, “숫자를 지우는” 방식이 강조됩니다.

조건에 따라 숫자를 지우는 것은 단순한 트릭처럼 보일 수 있지만, 분자와 분모가 모두 두 자리 숫자여야 하며, 숫자를 지운 뒤에도 원래의 분수 값이 유지되어야 하므로, 가능한 분수는 매우 제한적입니다.

문제는 이러한 조건을 만족하는 네 개의 분수를 모두 찾아서, 이 분수들을 곱한 뒤 기약분수로 만들고, 그 기약분수의 분모를 구하는 것입니다.

 

reduction of a fraction

 

이 문제는 분자와 분모에 같은 숫자를 추가하면, 약분이 되고, 약분된 결과가 원래 분수와 같으면 됩니다.

 

a/b 꼴의 분수에서는 분자 분모 양쪽 모두 뒤에 0을 추가하면 당연히 같은 값이 되겠죠.  이것은 당연한 해이므로 제해야 합니다.  그러려면, 분자에는 뒤에, 분모에는 앞에 어떤 숫자를 넣어주어야 합니다.  

 

a/b 라는 분수에 분자에는 앞에 분모에는 뒤에 숫자 x를 넣어준다면,

 

\[ \begin{align*}
a : b &= \frac{10x + a}{10b + x} \\
b(10x + a) &= a(10b + x) \\
x(10b - a) &= 9ab \\
x &= \frac{9ab}{10b - a} < a
\end{align*} \]

그 반대라면,

\[ \begin{align*}
a : b &= \frac{10a + x}{10x + b} \\
b(10a + x) &= a(10x + b) \\
x(10a - b) &= 9ab \\
x &= \frac{9ab}{10a - b} > b
\end{align*} \]

 

 

형태가 될겁니다.

 

결과는 비례식을 이용해서 단순하게 곱하면 나오므로, 푸는데에는 별 지장이 없을겁니다.

 

digit canceling fractions

 

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #33 - Digit Cancelling Fractions
//        - by Aubrey Choi
//        - created at 2015-03-20
//------------------------------------------------
#include <stdio.h>

int main()
{
    int n = 1, d = 1;
    for(int i = 2 ; i < 9 ; i++ )
    {
        for( int j = 1 ; j < i ; j++ )
        {
            for( int k = i+1 ; k < 10 ; k++ )
            {
                if( i*(j*10 + k) == j*(k*10+i) )
                    d *= k*10+i, n *= j*10+k;
                printf("%d %d %d\n", i, j, k);
            }
        }
    }

    int lcd = d;
    while( n )
    {
        int t = n;
        n = lcd%n;
        lcd = t;
    }
    printf("ans = %d\n", d/lcd);
}