[Project Euler] 36. 10진법과 2진법으로 모두 대칭수인 1,000,000 이하 숫자의 합

36. 10진법과 2진법으로 모두 대칭수인 1,000,000 이하 숫자의 합

대칭수(palindrome)인 585는 2진수로 나타내도 10010010012가 되어 여전히 대칭수입니다.

10진법과 2진법으로 모두 대칭수인 1,000,000 이하 숫자의 합을 구하세요.

(주의: 첫번째 자리가 0이면 대칭수가 아님)

Click
1~1000000까지의 수 중에 사실 대부분의 수는 대칭수가 아닙니다.
즉 이걸 모두 돌며 대칭수인지 아닌지를 판단하는 방법은 좋은 방법이 아니죠....
여기서 생각을 달리해 대칭수를 판단하는 것이 아닌... 대칭수를 만든다면??

1~999까지의 수를 해당 수의 자릿수만큼 뒤에 0을 붙이고 해당 수의 배열을 역으로 만들어 더해준다면?
즉, 1 -> 11, 12 -> 1221, 235->235532 로 만든다면 이것은 모두 대칭수가 됩니다.

1~999까지의 수를 자릿수 -1만큼 0을 붙인 후 가장 마지막 수를 제외한 수를 역으로 만들어 더해준다면??
즉 1 -> 1, 12 -> 121, 235 -> 23532. 이것도 역시 대칭수가 됩니다.

그리고 이 두 경우를 제외한 대칭수는 존재하지 않죠.

즉 1~1000000까지 존재하는 대칭수는 총 1998개가 전부입니다.
그럼 이 1998개의 수에 대해서 2진수가 대칭수인지를 판단하면 결과가 나오죠.

그리고 2진수가 대칭수가 되기위해 필요한 과정에서 10진수가 짝수라면 2진수의 1의자리에 0이 오게되어 대칭수가 아니게 되죠. 그래서 짝수를 걸러내면 조금더 효율적으로 구할 수 있습니다.

<script language="Javascript" type="text/javascript">
/* 수의 배열을 역으로 한 수. */
function reverse(number, base){
    var reverse = 0;
    while (number != 0) {
        reverse = reverse * base + number % base;
        number = parseInt(number/base);
    }
    return reverse;
}
/* 대칭수 판단. */
function isPalindromic(number, base) {
    return number == reverse(number, base);
}
/* 자릿수를 구함. */
function digit(n){
    return parseInt(Math.log(n)/Math.log(10))+1;
}
/* max값 보다 작은 수 중 2,10진수 모두가 대칭수 인 수를 모두 더해준 값. */
function p036(max){
    var sum = 0;
    for(var i=1; ; i++){
        var n = i* Math.pow(10,digit(i)) + reverse(i,10);
        if(n >= max) break;
        if(n % 2 == 0) continue;
        if(isPalindromic(n,2))
            sum += n;
    }
    for(var i=1; ; i++){
        var n = i* Math.pow(10,digit(i)-1) + reverse(parseInt(i/10),10);
        if(n >= max) break;
        if(n % 2 == 0) continue;
        if(isPalindromic(n,2))
            sum += n;
    }
    return sum;
}
</script>