C++로 숫자가 두 개의 삼각수의 합으로 표현 가능한지 확인하는 방법

이 글에서는 하나의 숫자가 두 개의 삼각수(Triangular Number)의 합으로 표현될 수 있는지 확인하는 방법을 알아보겠습니다.

삼각수란?

삼각수는 1부터 n까지의 자연수를 모두 더한 값으로 정의되는 수열입니다. 점을 삼각형 모양으로 배열했을 때 만들어지는 점의 개수와 같아서 '삼각수'라는 이름이 붙었습니다.

삼각수는 다음과 같은 형태로 나타납니다.

1, 3, 6, 10, 15, 21, ...

n번째 삼각수는 공식 T(n) = n × (n + 1) / 2로 구할 수 있습니다. 예를 들어 1, 3, 6, 10이 대표적인 삼각수입니다.

문제 정의

주어진 숫자 N(예: 16)을 두 개의 삼각수의 합으로 표현할 수 있는지 확인해야 합니다. 예를 들어 16은 삼각수인 6과 10의 합으로 표현할 수 있습니다.

접근 방법

풀이 방법은 매우 간단합니다.

1. N보다 작은 모든 삼각수를 구합니다.
2. 이 값들을 집합(set)에 저장합니다.
3. 집합에서 임의의 숫자 X를 선택하고, N − X도 집합 안에 존재하는지 확인합니다.
4. 존재한다면 N은 두 삼각수 X와 N − X의 합으로 표현 가능합니다.

C++ 구현 예제

#include <iostream>
#include <set>
using namespace std;

bool isSumTriangularNum(int n) {
    set<int> s;
    int i = 1;
    while (1) { // n 미만의 모든 삼각수를 찾아 집합에 저장
        int x = i * (i + 1) / 2;
        if (x >= n)
            break;
        s.insert(x);
        i++;
    }
    for (auto x : s)
        if (s.find(n - x) != s.end())
            return true;
    return false;
}

int main() {
    int num = 16;
    if (isSumTriangularNum(num)) {
        cout << "Can be represented";
    } else {
        cout << "Cannot be represented";
    }
}

실행 결과

Can be represented

코드 설명

isSumTriangularNum 함수는 먼저 while 루프를 통해 n보다 작은 모든 삼각수를 계산하여 set에 저장합니다. 그다음 집합의 각 요소 x에 대해 n - x가 집합에 존재하는지 find() 함수로 확인합니다. 존재하면 true를 반환하고, 모든 조합을 확인한 후에도 없으면 false를 반환합니다.

예제에서 입력값 16은 6 + 10으로 표현되므로 "Can be represented"가 출력됩니다.

시간 복잡도

삼각수 생성에는 O(√N) 시간이 걸리고, 각 삼각수에 대해 집합 탐색은 O(log N)이므로 전체 시간 복잡도는 약 O(√N log N)입니다. 집합을 사용하기 때문에 탐색이 효율적으로 처리됩니다.