[C/C++] 프로젝트 오일러 #45 삼각수, 오각수, 육각수

Project Euler 문제 45번은 특정한 수열들 간의 관계를 탐색하는 문제입니다.

이 문제에서는 삼각수(Triangular number), 오각수(Pentagonal number), 육각수(Hexagonal number)의 개념을 다루고 있습니다. 삼각수는 자연수의 합으로 정의되며, 식으로는  \(T_n = \frac{n(n+1)}{2}\) 로 나타낼 수 있습니다. 오각수는 특정 패턴을 따라 증가하는 다각수 중 하나로,  \(P_n = \frac{n(3n-1)}{2}\) 의 형태를 가집니다. 육각수는 정육각형 패턴을 따라 증가하며, 식으로는  \(H_n = n(2n-1)\) 로 정의됩니다.

문제에서는 이 세 가지 수열의 교집합을 찾는 것이 목표입니다. 이미 주어진 예시로  \(T_{285} = P_{165} = H_{143} = 40755\) 가 유일한 공통 숫자로 주어져 있습니다. 여기서 요구하는 바는 40755보다 크면서도 다시 삼각수, 오각수, 육각수의 공통 원소가 되는 다음 숫자를 찾는 것입니다.

이를 해결하기 위해서는 세 가지 수열을 생성하고, 이를 비교하는 방식으로 접근할 수 있습니다. 효율적인 계산을 위해 특정 패턴을 활용하여 중복된 연산을 줄이는 것이 중요합니다.

 

삼각수, 오각수, 육각수라는 것은 앞에 #44(http://sdev.tistory.com/224)에서 설명한 것과 같이 도형을 그릴 때, 발생하는 점들의 갯수입니다.

 

삼각수를 기준으로 하든지, 육각수를 기준으로 하든지, 다른 숫자들을 맞추어 나가면 됩니다.  제 경우에는 삼각수와 오각수를 먼저 맞추고 다음 육각수를 맞추는 방식을 이용했습니다.  예를 들어서 삼각수와 오각수가 a라는 값으로 같으면, 육각수를 증가시켜서 그 수를 맞춥니다. 육각수가 a라는 값을 넘어서게 되면 삼각수를 증가시킵니다.

 

간단하게 공차식을 구해서 계산하는 것이 편하겠죠.  삼각수는 1부터 N까지 모두 더한 값이므로 공차식은 N이 됩니다.  즉, 매번 증가할 때마다 공차값이 1씩 증가하면 됩니다.  오각수는 3씩 증가하면 되고 육각수는 4씩 증가하면 됩니다.

 

Triangular Number

 

그래서 만들어진 소스는 다음과 같습니다.

//------------------------------------------------
//    Project Euler #45 - Triangular, Pentagonal, and Hexagonal
//        - by Aubrey Choi
//        - created at 2015-03-29
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>

int main()
{
    uint64_t t = 40755, p = 40755, h = 40755;
    uint64_t dt = 286, dp = 496, dh = 573;

    t += dt; dt++;
    while( 1 )
    {
        if( t < p ) { t += dt; dt++; }
        else if( p < t ) { p += dp; dp += 3; }
        else if( h < p ) { h += dh; dh += 4; }
        else if( t < h ) { t += dt; dt++; }
        else break;
    }
    printf("ans = %ju\n", t);
}