C++로 삼각수(Triangular Number)인지 판별하는 방법

어떤 자연수 n이 주어졌을 때, 이 수가 삼각수(triangular number)인지 판별하는 문제입니다. 삼각수란 n개의 점(또는 공)을 층층이 배열하여 정삼각형 형태로 만들 수 있는 수를 의미합니다. k번째 삼각수는 1부터 k까지의 합, 즉 k × (k + 1) / 2로 계산됩니다.

예를 들어, 입력이 n = 10이라면 결과는 참(True)이 됩니다. 1 + 2 + 3 + 4 = 10이므로 10은 네 번째 삼각수에 해당합니다.

풀이 접근 방법

이 문제는 간단한 반복문으로 해결할 수 있습니다. i를 1부터 n까지 증가시키면서 i × (i + 1)이 2n과 같아지는 경우가 존재하는지 확인하면 됩니다. 그러한 i가 있다면 n은 삼각수입니다.

for initialize i := 1, when i <= n, update (increase i by 1), do:
    if i * (i + 1) is same as 2 * n, then:
        return true
return false

C++ 구현 예제

다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;
bool solve(int n){
    for (int i = 1; i <= n; i++){
        if (i * (i + 1) == 2 * n){
            return true;
        }
    }
    return false;
}
int main(){
    int n = 10;
    cout << solve(n) << endl;
}

입력

10

출력

1

보너스: O(1) 시간에 판별하는 수학적 방법

위 반복문 기반 풀이의 시간 복잡도는 O(n)입니다. 하지만 수학적 성질을 활용하면 상수 시간에 판별할 수 있습니다. 어떤 수 n이 삼각수일 필요충분조건은 8n + 1이 완전제곱수라는 것입니다. 예를 들어 n = 10일 때 8 × 10 + 1 = 81 = 9²이므로 10은 삼각수임을 바로 알 수 있습니다.