[Project Euler] 33. 이상한 방법으로 약분할 수 있는 분수 찾기

33. 이상한 방법으로 약분할 수 있는 분수 찾기

분수 49/98에는 재미있는 성질이 있습니다. 수학을 잘 모르는 사람이 분모와 분자에서 9를 각각 지워서 간단히 하려고 49/98 = 4/8 처럼 계산해도 올바른 결과가 됩니다.

이에 비해 30/50 = 3/5 같은 경우는 다소 진부한 예라고 볼 수 있습니다.

위와 같은 성질을 가지면서 '진부하지 않은' 분수는, 값이 1보다 작고 분자와 분모가 2자리 정수인 경우 모두 4개가 있습니다.

이 4개의 분수를 곱해서 약분했을 때 분모는 얼마입니까?

Click
우선 관계를 간단히 하기위해 10의 자리와 1의 자리를 분리하면 (10a+b)/(10b+c) = a/c 가 되고... 이를 좀더 분자 분모를 정리하고, 위에 조건에서 알 수 있는 a,b,c의 범위를 표시하면....

(10a+b)/(10b+c) = a/c
9ac + bc = 10ab
9a + b = 10ab/c

0 < a <= b < 10
0 < a < c < 10

위의 a,b,c범위에서 9a+b=10ab/c 를 만족하는 수를 구해 분모와 분자를 따로 곱한 후 최종적으로 구한 분모, 분자의 최대공약수를 구해서 분모/최대공약수 를 하면 원하는 결과를 얻을 수 있습니다.

<script language="Javascript" type="text/javascript">
function p033(){
    var d = 1, n = 1;       //d:분수  n:분모.
    
    for(var a=1; a<9; a++){
        for(var b=a; b<10; b++){
            for(var c=a+1; c<10; c++){
                if(9*a + b == 10*a*b/c){    //조건 만족시 분수 분모 곱해줌.
                    d *= 10*a + b;
                    n *= 10*b + c;
                }
            }
        }
    }
    
    var g = gcd(d,n);   //약분을 위해 최대공약수를 구함.
    alert(n/g);
}
</script>

최대 공약수는 이전에도 자주 사용 했던 유클리드 호제법을 이용했습니다.

<script language="Javascript" type="text/javascript">
function euclid(a,b){
 if (b == 0) return a;
 return euclid(b, a % b);
}
function gcd(a,b){
 return euclid(Math.max(a,b),Math.min(a,b));
}
</script>