14. 프로젝트 오일러 #14 : 최대 체인을 가지는 우박수 구하기
이번 문제는 동적 프로그래밍을 이용해서 작성을 하는 것이 가장 좋을 듯 합니다. 우박수를 구하다보면, 이미 전에 계산했던 우박수 체인수가 있을 수 있습니다. 그렇게 하지 않으면, 체인수가 100여개 있는데, 1,000,000까지 구한다면, 1억번정도 평균적으로 계산해야 합니다. 동적 프로그래밍을 이용하면, 이 수를 줄일 수 있습니다. 물론 수가 1이 된다는 가정하에서 이야기지만, 현재까지 예외는 없으니까요. 사실 수학적으로 1,000,000까지 우박수가 된다는 것을 확인하면, n/2로 건너뛰기를 하기 때문에 반드시 우박수가 될 수밖에 없습니다. 순수한 수학적인 증명만으로는 할 수 없지만요. 물론, 자꾸 홀수에 걸쳐서 숫자가 비대해질 수는 있습니다만, 3n+1 은 반드시 짝수가 되기 때문에 홀수가 연달아 ..
2014. 12. 30.