Script / CSS

G1sUtil.js

G1sBlogger.js

CSS

G1sNavigationList.js

Posts List


2012년 4월 13일 금요일

[Project Euler] 44. 합과 차도 모두 오각수인 두 오각수 차의 최소값은?

44. 합과 차도 모두 오각수인 두 오각수 차의 최소값은?

오각수는 Pn = n (3n − 1)/2 라는 공식으로 구할 수 있고, 처음 10개의 오각수는 다음과 같습니다.

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

위에서 P4 + P7 = 22 + 70 = 92 = P8이 됨을 볼 수 있습니다. 하지만 두 값의 차인 70 − 22 = 48 은 오각수가 아닙니다.

합과 차도 모두 오각수인 두 오각수 Pj, Pk 에 대해서, 그 차이 D = | Pk − Pj | 는 가장 작을 때 얼마입니까?
Click

일단 문제를 해결 하기 위해 오각수를 판단하는 함수가 일단 필요하겠네요.
x = n(3n-1)/2
2x = 3n²- n
24x = 36n²- 12n
24x + 1 = 36n²- 12n +1
24x + 1 = (6n - 1)²
√(24x + 1) = 6n - 1
√(24x + 1) + 1 = 6n
(√(24x + 1) + 1) / 6 = n
즉 위의 값 n이 정수값을 가지면 해당 수 x는 오각수가 됩니다.
<script language="Javascript" type="text/javascript">
/** 오각수 판단. **/
function isPentagonal(num){
    var n = (Math.sqrt(24*num + 1)+1)/6;
    if(parseInt(n) == n)
        return true;
    else
        return false;
}
</script>
이제 남은 것은 범위를 정하는 것인데요. k>j 이고, j는 최대 k-1 이니 d값은 최소 P(k) - P(k-1) 값이고, 이 값은.. 3k - 2 가 됩니다.
p(n) - p(n-1) = (n(3n-1) - (n-1)(3(n-1)-1))/2
p(n) - p(n-1) = (3n²- n - (3n²- 7n + 4))/2
p(n) - p(n-1) = 3n - 2
즉 3k-2가 min 보다 크다면 더 이상의 k값의 증가 탐색을 할 필요가 없겠죠.
그리고 j값은 k-1부터 시작해 d값이 min보다 크면 탐색 종료, P(j)가 3*k-2보다 작으면 d값은 오각수가 아니게 되므로 마찬가지로 탐색을 종료합니다.
<script language="Javascript" type="text/javascript">
/** 오각수. **/
function pentagonal(n){
    return (3*n*n - n)/2;
}
function p044(){
    var min = 1000000000;
    
    for(var k=2; 3*k-2<min; k++){
        var pk = pentagonal(k), d = 0, s;
        for(var j=k-1; j>0; j--){
            var pj = pentagonal(j);
            d = pk - pj;
            if(d>min)
                break;
            else if(pj<3*k-2)
                break;
            else if(isPentagonal(d) && isPentagonal(pk+pj))
                min = d;
        }
    }
    alert(min);
}
</script>
돌려보면 체감상으로도 바로 값이 안나오는 것이 느껴질 정도로 연산이 꽤 오래 걸리는 편입니다.

해당 조건을 만족하는 최초의 d 값이 가장 작은 값이라는 것은 예상이 가능하고 해당 d를 구하는 것은 빠른 편인데,
해당 d값이 과연 가장 작은 값인지에 대해, 그 이상의 값을 탐색하는게 오래걸리는 편이네요.

예상대로 첫번째 d가 가장 작은 수가 맞고.. 범위를 임의로 자르거나 첫번째로 구하는 d까지만 탐색한다면 더 빠른 시간이 걸리겠지만 해당 방법은 답은 맞을지라도 문제를 제대로 푼 것은 아니겠지요.

어떻게든 범위를 줄이는 것이 관건인데 더이상의 좋은 방법은 떠오르지 않는 군요.

댓글 4개:

  1. 안녕하세요, 잘 보았습니다. 그런데 'P(j)가 3*k-2보다 작으면 d값은 오각수가 아니게 된다' 이 부분이 잘 이해가 안 가네요. 부연 설명 부탁드려요 ㅠㅠ

    답글삭제
    답글
    1. 답변이 늦었네요. 죄송합니다.
      k 번째 오각수가 P(k) 일때 P(k) 바로 전 오각수 P(k-1) 과의 차가 3*k-2 라는것은 그 위에 증명이 되었습니다.
      이는 즉 P(k) 에서 3k-1 보다 작은 값을 빼면 P(k-1) 값과 P(k) 값 사이의 오각수가 아닌 값이 나오게 되는거죠. ^^

      삭제
  2. 그리고 다른 풀이에 보면 처음 나오는 d 값을 답으로 했던데, 왜그런지 이해가 안 됩니다. p97 - p20 > p100 - p99 이고 둘 다 오각수인 경우 같은 것은 없는 건가요? 답변해주시면 정말 감사하겠습니다!

    답글삭제
    답글
    1. 제가 이곳에 Project Euler 를 올리는 것은 제 답이 정답이다. 라고 올리는게 아니라. 저는 이렇게 풀었습니다. 라는 의미로 올리는 것입니다. 저도 정답을 정확히 아는 것은 아니라서요.
      처음 나오는 d값이 정답일 거라고는 저도 예상은 되나 그 값이 정답일거라는 확신은 저도 없기에 이렇게 반복문을 최대한 줄이는 쪽으로 간 것이죠. (그래도 길지만요..)
      그걸 유추해서 공식으로 풀어내시는 분이 있다면 그것이 정답이 겠지요. ^^

      삭제