Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

G1sTagList

Posts List

2012년 4월 1일 일요일

[Project Euler] 034. 각 자릿수의 팩토리얼을 더했을 때 자기 자신이 되는 수들의 합은?

34. 각 자릿수의 팩토리얼을 더했을 때 자기 자신이 되는 수들의 합은?
숫자 145에는 신기한 성질이 있습니다. 각 자릿수의 팩토리얼(계승)을 더하면 1! + 4! + 5! = 1 + 24 + 120 = 145 처럼 자기 자신이 됩니다.

이렇게 각 자릿수의 팩토리얼을 더하면 자기 자신이 되는 모든 수의 합을 구하세요.

단, 1! = 1 과 2! = 2 의 경우는 덧셈이 아니므로 제외합니다.

Click
123, 132, 213, 231, 312, 321의 각자리수를 !해준 후 더해준 값 fsum은 같다.
그러므로 10~max까지 값을 증가시켜가며 확인하는 것보다 특정 숫자들의 fsum을 구한 후 sum이 특정 숫자들의 조합으로 만들어질 수 있는지를 확인하는게 빠를 수도 있다.
그리고 대부분의 경우 자릿수부터가 다르므로 자릿수로 걸러낸다면 확실한 단축효과를 줄 수 있을 것이다.
라는 가정아래 구현했는데 과연 얼마나 단축 효과를 줄 수 있을지는...

일단 한번 체크한 수를 중복 체크하지 않기 위해 작은값부터 체크하며 자기보다 같거나 높은 수로만 이루어진 배열을 찾는 방법과 높은값부터 체크하며 자기보다 작은 수로 이루어진 수의 배열을 찾는 방법 두 가지 중에 더이상 배열을 확장하지 않아도 되는 지점을 찾기위해 2번째 방법 높은 값부터 체크하며 자기보다 작은 수로 이루어진 수의 배열을 찾는 방법을 사용했습니다.

더해서 factorial값의 중복 계산을 막기 위해 미리 factorial의 값들을 구해서 배열에 저장.
<script language="Javascript" type="text/javascript">
/* 숫자 조합을 확장해 나가는 재귀함수. */
function func034(f, nums, n, digit, sum){
    var r = 0;
    /* 자릿수 체크와 nums의 숫자가 있는지를 확인하기 편하도록 string형으로 변환. */
    var str = sum.toString();
    if(digit > str.length)//sum 자릿수가 nums 갯수보다 많다면 더이상 확장은 무의미.
        return 0;
    else if(digit == str.length){   //자릿수가 같은 경우에만 조건 판단.
        for(var i=0; i< digit; i++){
            var k = str.indexOf(nums[i].toString());
            if(k < 0)
                break;
            str = str.substr(0,k) + str.substr(k+1, str.length);//일치 값 제거.
        }
        if(str == "")   //조합이 일치하는 값이 있다면 결과값에 sum값 더해 줌.
            r += sum;
    }
    /* 자신보다 작은 수들의 한해서 새로운 조합을 찾음. */
    for(var i=n; i>=0; i--){
        nums[digit] = i;
        r += func034(f, nums, i, digit+1, sum+f[i]);
    }
    
    return r;
}
function p034(){
    //점화식[(n + 1)! = n! × (n + 1) , 0!=1]에 의해 factorial 의 값을 미리 구함.
    var f = new Array();
    f[0] = 1;
    for(var i=1; i<10; i++)
        f[i] = i * f[i-1];
    
    var r = 0;

    //숫자 조합 확장 시작.
    var nums = new Array();
    for(var i=9; i>0; i--){
        nums[0] = i;
        r += func034(f, nums, i, 1, f[i]);
    }
    r -= 3;     //1과 2의 값은 제외해야하므로 r에서 빼줌.
    
    alert(r);
}
</script>

댓글 3개:

  1. 안녕하세요 또 들렸습니다. ^^

    답글삭제
  2. 시간이 되신다면 제 블로그 한번 들려주세요.
    여기서 배운것들 적용해봤습니다^^

    답글삭제
    답글
    1. 블로그가 어딘지 몰라서요. ㅎㅎ 프로필에 있는곳 따라갔더니 프로필에 있는 블로그는 없는 블로그라고 나오네요. ^^

      삭제