[PHP] 프로젝트 오일러 - 14

[ProjectEuler.net 원본]

출제 일시 : 2012-01-03 19:11:35

양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.

n → n / 2 (n이 짝수일 때)
n → 3 n + 1 (n이 홀수일 때)

13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다. 
(역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)

그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까?

참고: 계산 과정 도중에는 숫자가 백만을 넘어가도 괜찮습니다.

음.. 그냥 2개 반복문으로 돌려서 할 수 있겠지만, 기본적으로 100만번의 반복에 한번씩만 더 돌아도 100만번이 추가가 되는데요.

최소한의 알고리즘을 찾아내기 위해 일단 무식하게 해보겠습니다.

n의 수를 13이라고 가정했을때, 

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1  (10)

n의 수를 14라고 가정했을때,

14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (18)

여기에서 공통점을 찾아보면 앞서나왔던 수의 기점으로 부터 같아진다는걸 알 수 있습니다.

그렇다는 것은 앞서 나왔던 수가 나온다면 그 뒤는 굳이 반복문을 돌릴 필요가 없다는 것이겠죠

그렇다면 그 뒤의 수는 어떻게 처리하느냐!

배열을 사용하여 값을 기준으로 카운터를 저장해두면 됩니다.

다시 예로 돌아가자면

n의 수를 13이라고 가정했을때, 

배열 [13] => 10, [40] => 9, [20] => 8, [10] => 5 ... 

이처럼 배열로 저장을 해둔 뒤 앞서 나왔던 수가 다시 나온다면..

n의 수를 14라고 가정했을때,

14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 (배열 [13] => 10)

그 수의 기점으로 +해주시면 됩니다.

말로는 너무나 간단한 알고리즘이죠?

이 과정을 코딩으로 옮겨보도록 하겠습니다.

function get_cnt($num, $arr){

    $cnt = 0;

    while($num != 1){

        if(isset($arr[$num])){

            $cnt += $arr[$num];

            break;

        }

        if($num%2) $num = $num * 3 + 1;

        else $num /= 2;

        $cnt++;

    }

    return $cnt;

}

$arr = array();

$num = 1;

while($num <= 1000000){

    

    $cnt = get_cnt($num, $arr);

    $arr[$num] = $cnt;

    $num++;

}

echo array_search(max($arr), $arr);

이렇게 간단하게 해결됩니다!