Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List


2012년 3월 23일 금요일

[Project Euler] 32. 1~9 팬디지털 곱셈식을 만들 수 있는 모든 수의 합

32. 1~9 팬디지털 곱셈식을 만들 수 있는 모든 수의 합

1부터 n까지의 각 숫자를 한번씩만 써서 만들 수 있는 숫자를 팬디지털(pandigital)이라고 합니다.
예를 들면 15234는 1부터 5의 숫자가 한번씩만 쓰였으므로 1 ~ 5 팬디지털입니다.

7254라는 숫자는 그런 면에서 특이한데, 39 × 186 = 7254 라는 곱셈식을 만들 때 이것이 1 ~ 9 팬디지털이 되기 때문입니다.

이런 식으로 a × b = c 가 1 ~ 9 팬디지털이 되는 모든 c의 합은 얼마입니까?

(참고: 어떤 c는 두 개 이상의 (a, b)쌍에 대응될 수도 있는데, 이런 경우는 하나로 칩니다)

Click
진짜 대충 풀었네요.
사실 요 몇일 나름 바쁜 사정으로 인해 Project Euler 하루 한개씩 올리기로 한 개인 과제를 쉬기로 했습니다. Project Euler를 안하니 블로그 업뎃이 뜸하기도 하고 해서 오랜만에 한문제 풀었는데 좀 귀찮은 문제가 걸렸네요. 머리에서 더 좋은 방법이 떠오르지만 제대로 구현은 안되고 딴 생각만 나고....
<script language="Javascript" type="text/javascript">
function p032_in(){
    var n = 9;
    var sum = 0;
    for(var c=1234; c<=9876; c++){
        /* 팬디지털 체크를 위한 변수들 선언. */
        var check = true;
        var nums = new Array();
        for(var i=1; i<=n; i++)
            nums[i] = true;
        nums[0] = false;

        /* c값이 팬디지털에 적용되는지 확인. */
        var temp1 = c;
        do{
            var temp2 = temp1%10;
            if(!nums[temp2]){
                check = false;
                break;
            }
            nums[temp2] = false;
            temp1 = parseInt(temp1/10);
        }while(temp1!=0);
        if(check){                //c값이 팬디지털를 만족하면 a값 구함.
            for(var a=1; a<=98;a++){
                check = true;

                /* c값에 사용된 숫자 채움. */
                for(var i=1; i<=n; i++)
                    nums[i] = true;
                temp1 = c;
                do{
                    var temp2 = temp1%10;
                    nums[temp2] = false;
                    temp1 = parseInt(temp1/10);
                }while(temp1!=0);
                /*a값이 팬디지털을 만족하는지 확인.*/
                temp1 = a;
                do{
                    var temp2 = temp1%10;
                    if(!nums[temp2]){
                        check = false;
                        break;
                    }
                    nums[temp2] = false;
                    temp1 = parseInt(temp1/10);
                }while(temp1!=0);
                if(check){        //a,c값이 모두 팬디지털을 만족한다면 b값을 구함.
                    check = true;
                    var b = c / a;
                    
                    if(b-parseInt(b)!=0){ //c가 a로 딱 나눠떨어지는지 확인.
                        check = false;
                        continue;
                    }
                    //b값이 팬디지털을 만족하는지 확인.
                    temp1 = b;
                    do{
                        var temp2 = temp1%10;
                        if(!nums[temp2]){
                            check = false;
                            break;
                        }
                        nums[temp2] = false;
                        temp1 = parseInt(temp1/10);
                    }while(temp1!=0);
                    if(check){
                        //모든 수를 사용했는지 확인.
                        for(var i=1; i<=n; i++){
                            if(nums[i]){
                               check = false;
                                break;
                            }
                        }
                        //최종적으로 팬디지털을 만족한다면 c값을 더해 줌.
                        if(check)
                            sum += c;
                    }
                }
                if(check)
                    break;
            }
        }
    }    
    
    alert(sum);
}
</script>

댓글 없음:

댓글 쓰기