[Project Euler] 38. 어떤 수에 (1, 2, ... )를 곱해서 이어붙여 얻을 수 있는 가장 큰 1 ~ 9 팬디지털 숫자

38. 어떤 수에 (1, 2, ... )를 곱해서 이어붙여 얻을 수 있는 가장 큰 1 ~ 9 팬디지털 숫자

숫자 192에 1, 2, 3을 각각 곱합니다.

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
곱한 결과를 모두 이어보면 192384576 이고, 이것은 1 ~ 9 팬디지털(pandigital)인 숫자입니다. 이런 과정을 편의상 '곱해서 이어붙이기'라고 부르기로 합니다.

같은 식으로 9와 (1, 2, 3, 4, 5)를 곱해서 이어붙이면 918273645 라는 1 ~ 9 팬디지털 숫자를 얻습니다.

어떤 정수와 (1, 2, ... , n)을 곱해서 이어붙였을 때 얻을 수 있는 가장 큰 아홉자리의 1 ~ 9 팬디지털 숫자는 무엇입니까? (단 n > 1)

Click
두가지 방법으로 풀었는데요.

우선 풀이에 들어가기에 앞서 기본적으로 사용한 함수는...

자릿수를 알아내는 함수

<script language="Javascript" type="text/javascript">
function getDigit(n){
    return Math.ceil(Math.log(n)/Math.log(10));
}
</script>

주어진 값을 n까지 곱해서 이어붙이는 함수

<script language="Javascript" type="text/javascript">
function joinMultiply(m, n){
    var r = m;
    for(var i=2; i<=n; i++){
        var temp = m * i;
        var digit = getDigit(temp);
        r = r * Math.pow(10,digit) + temp;
    }
    return r;
}
</script>

각 자릿수를 이루고 있는 수 중 0이나 중복 된 수가 없는지를 판단하는 함수.

<script language="Javascript" type="text/javascript">
function checkNoneOverlapNum(n){
    var temp = n;

    var check = new Array();
    check[0] = false;
    for(var j=1; j<10; j++)
        check[j] = true;
    
    while(temp >= 1){
        var t = temp % 10;
        if(check[t])
            check[t] = false;
        else
            return false;
        temp = parseInt(temp/10);
    }
    return true;
}
</script>

이상 3가지.
각 자릿수를 이루고 있는 수 중 0이나 중복 된 수가 없는지를 판단하는 함수는 팬디지털 판단 외에도 전처리로 사용하기 위해 9자리 모두를 썼는지 확인하는 과정은 제외된 상태이죠.
이 3 함수를 기본으로 하여 이제는 탐색 범위를 줄이는 것이 관건. 

우선 첫번째 방법은 주어진 힌트를 모두 이용하는 방법입니다.

힌트에 주어진 값중에 9, (1~5) 곱 이어붙인 값이 918273645가 현재까지 알고있는 최대값입니다.
그렇다면 최소한 첫자리가 9로 시작하는 자리이고,

90,(1~4) 곱 이어붙이기는 11자릿수, 99,(1~3) 곱 이어붙이기는 8자릿수로 90대 탐색 필요없음.
900, (1~3) 곱 이어붙이기는 11자릿수, 999, (1~2) 곱 이어붙이기는 7자릿수로 900대 탐색 필요없음.
9000, (1~2) 곱 이어붙이기는 9자릿수. 9999, (1~2) 곱 이어붙이기는 9자릿수로 9000대 탐색 필요.

그리고, 최소 9182보다 커야 하므로 9183부터 탐색 시작.
9876보다 큰 수로는 팬디지털이 안되므로 9876까지 탐색.
여기에 더해서 i의 값 각 자릿수에 겹치는 수가 있거나 0이 있다면 팬디지털을 만들 수 없으므로 해당 수는 제외.

위와 같은 식으로 탐색 범위를 줄여서 탐색을 합니다.

<script language="Javascript" type="text/javascript">
function p038(){
    var max = joinMultiply(9,5);
    
    for(var i=parseInt(max/100000); i<9876; i++){
        if(!checkNoneOverlapNum(i))
            continue;
        
        var join = joinMultiply(i,2);
        if(checkNoneOverlapNum(join)){
            if(join > max)
                max = join;
        }
    }
    alert(max);
}
</script>

위 방식으로 간단히 구하기는 했는데.... 솔직히 저 방식은 제가 좋아하는 방식은 아니네요.
힌트로 주어진 값이 9,(1~5)의 경우가 아니었다면 저 방식으로는 못 푸는 경우도 발생하겠죠.
그래서, 이 힌트에는 상관없이 주어진 조건만으로 값을 구해내는 방식이 두번째 방식입니다.

일단 주어진 조건에 만족하는 팬디지털이 있다는 가정아래 max값은 123456789로 초기화 합니다.

탐색은 각 1부터 n이 최소 2가 될 수 있는 조건인 9876까지 탐색하는 방법이 있으나, 탐색 과정을 줄이기 위해 자릿수로 탐색.

즉 한자리인 1~9까지 탐색,
두자리인 11~99까지 탐색.
세자리 101~999까지 탐색.
네자리 1001~9999까지 탐색.

하는 것을 기본 틀로 잡습니다. 
그리고 다시 각 자리수 탐색의 시작지점을 현재 max값의 가장 앞자리로 이루어진 값 +1로 재 조정합니다. 즉.

i = max/100000000*(pow(10,자릿수))+1

이 시작 점이 됩니다. (이를 편하게 계산하기 위해 v값을 자릿수 증가시마다 10씩 곱해주며 판단.)

 다음으로 각 수마다 적정 필요 n값을 구하는데... 
n은 1부터 순서대로 곱했을때 자릿수가 바뀌는 지점을 파악(해당 점은 k로 볼때)
해당 지점까지로 구할 수 있는 자릿수를 뺀 나머지 자릿수로 9를 만들 수 있는 수를 찾으면 된다.
라는 결론아래 아래 식이 나옵니다.

n = k + (9-(k*digit))/(digit+1) 

그리고 해당 n값이 자연수가 아닐 경우, 해당 값은 9자리를 만들지를 못한다는 뜻이고, 이를 한번 걸러냅니다.

마지막으로 첫번째 방식에 사용한 i의 값 각 자릿수에 겹치는 수가 있거나 0이 있다면 팬디지털을 만들 수 없으므로 해당 수는 제외

이 와 같은 방법으로 탐색 범위를 좁힐 수 있습니다.

<script language="Javascript" type="text/javascript">
function p038(){
    var max = 123456789;
    
    var v = 1;
    for(var digit = 1; digit < 10/2; digit++){
        v *= 10;
        for(var i=parseInt(max/100000000*(v/10))+1; i<v; i++){
            var n = parseInt(v/i);
            n += (9-n*digit)/(digit+1);
            
            if(n != parseInt(n))
                continue;
            
            if(!checkNoneOverlapNum(i))
                continue;
            
            var join = joinMultiply(i,n);
            if(checkNoneOverlapNum(join)){
                if(join > max)
                    max = join;
            }
        }
    }
    alert(max);
}
</script>

딱 보기에도 두번째 방식이 첫번째 방식보다 오래걸리는 것은 확실 합니다.
하지만, 1~9까지 탐색을 마치고 나면 max값이 918273645로 변하게 되고, 이것은 후에 탐색범위를 줄이는 큰 역할을 하죠.

그리고 이렇게 좁힌 범위 안에서는 n의 값을 구하는 판별법만으로 2자릿수 대와 3자릿수대를 모두 걸러낼 수 있습니다.

즉, 결국 1~9 탐색 후 92~99까지, 919~999까지는 n판별까지만 탐색하고, 9183부터 다시 탐색에 들어가
1번째 방법에 비해 큰 차이가 나지 않는다고 볼 수 있겠네요.