[Project Euler] 30. 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은?

30. 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은?

각 자리의 숫자를 4제곱해서 더했을 때 자기 자신이 되는 수는 놀랍게도 단 세 개밖에 없습니다.


1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴
(1 = 14의 경우는 엄밀히 말해 합이 아니므로 제외합니다)

위의 세 숫자를 모두 더하면 1634 + 8208 + 9474 = 19316 입니다.

그렇다면, 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은 얼마입니까?

Click

깊이 탐색으로 탐색해 내려가면서 현재 수가 각자리수를 5제곱해서 나온 값보다 작으면 새로운 수를 더해 줄 수 있다고 판단 *10을 한 후 1에 자리에 새로운 수를 더해주고...
현재수가 각자리수를 더한 수보다 크다면 더이상 수를 더해주면 안돼니 깊이 탐색을 끝내는... 분기 한정 가지치기 깊이탐색법입니다.

분기 한정법(分岐限定法, Branch and bound)은 다양한 최적화 문제를 풀기 위한 범용 알고리즘이다. 주로 이산 최적화나 조합 최적화 문제를 풀 때 쓴다. 분기 한정법은 모든 후보해를 체계적으로 늘어놓으면서 최적화할 수치의 상한과 하한을 추정, 가망 없다는 판정이 나는 해를 제거해 나간다. 제거하는 해에서 파생되는 해는 살펴보지 않기 때문에 불필요한 시간 소모를 줄이게 된다.
이 방법은 A. H. 랜드와 A. G. 도이그가 1960년에 선형 계획법을 풀기 위해서 제안하였다.

위키백과 : 분기한정법

<script language="Javascript" type="text/javascript">
/* 분기한정 가지치기 깊이 탐색. */
function branchNbound(nums,n,sum){
    if(n > sum) //분기 한정. (n이 각 자리수의 5제곱의 합보다 크면 탐색실패.)
        return 0;
    else if(n == sum && n!=1) //찾은 결과 return.
        return sum;
    
    //0~9까지의 경우에 대해 가지를 탐색.
    var nsum = 0;
    for(var i=0; i<10; i++){
        var tn = n*10 + i;
        var tsum = sum + nums[i];
        nsum += branchNbound(nums, tn, tsum);
    }
    return nsum;
}
function p030(n){
    //input으로 들어 온 n값에 대한 각 n제곱값들을 저장.
    var nums = new Array();
    for(var i=0; i<10; i++)
        nums[i] = Math.pow(i, n);
    
    //가지 탐색 시작.
    var sum = 0;
    for(var i=0; i<10; i++)
        sum += branchNbound(nums, i, nums[i]);
    
    return sum;
}
</script>