C++로 약수의 개수가 N을 초과하는 첫 번째 삼각수 찾기

이 튜토리얼에서는 약수의 개수가 n보다 큰 첫 번째 삼각수를 찾는 방법을 알아보겠습니다.

먼저 삼각수(Triangular Number)란 무엇인지 간단히 짚고 넘어가겠습니다. 삼각수란 1부터 어떤 자연수 k까지의 합으로 표현할 수 있는 수를 말합니다. 즉, T(k) = 1 + 2 + 3 + ... + k = k × (k + 1) / 2 형태로 나타낼 수 있는 수입니다. 예를 들어 1, 3, 6, 10, 15 등이 삼각수에 해당합니다.

그렇다면 주어진 수가 삼각수인지 어떻게 판별할 수 있을까요? 임의의 지점까지 자연수의 합이 그 수와 같아진다면, 그 수는 삼각수라고 할 수 있습니다.

문제 해결 절차

삼각수에 대한 개념을 이해했으니, 이제 문제를 해결하는 단계를 살펴보겠습니다.

탐색을 시작할 숫자를 초기화합니다.
주어진 조건을 만족하는 수를 찾을 때까지 반복문을 실행합니다.
현재 수가 삼각수인지 확인합니다.
현재 수의 약수 개수가 n보다 많은지 확인합니다.
위 두 조건을 모두 만족하면 해당 수를 출력하고 반복문을 종료합니다.

구현 예제

위 절차를 C++ 코드로 구현한 예제를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;

// 삼각수 여부를 판별하는 함수
bool isTriangular(int n) {
    if (n < 0) {
        return false;
    }
    int sum = 0;
    for (int i = 1; sum <= n; i++) {
        sum += i;
        if (sum == n) {
            return true;
        }
    }
    return false;
}

// 약수의 개수를 세는 함수
int divisiorsCount(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            count += 1;
        }
    }
    return count;
}

int main() {
    int n = 2, i = 1;
    while (true) {
        if (isTriangular(i) && divisiorsCount(i) > 2) {
            cout << i << endl;
            break;
        }
        i += 1;
    }
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

결과가 6인 이유를 살펴보겠습니다. 6은 1 + 2 + 3의 합으로 표현되는 삼각수이며, 약수는 1, 2, 3, 6으로 총 4개입니다. 약수의 개수 4는 n = 2보다 크므로, 6이 조건을 만족하는 첫 번째 삼각수가 됩니다.

성능 개선 팁

위 코드는 단순하지만, 약수의 개수를 셀 때 1부터 n까지 모든 수를 검사하기 때문에 비효율적일 수 있습니다. 약수는 쌍으로 존재한다는 점을 활용해 √n까지만 검사하면 시간 복잡도를 O(n)에서 O(√n)으로 줄일 수 있습니다. 또한 삼각수 판별 시에도 k(k+1)/2 공식을 역으로 활용하면 더 빠르게 확인할 수 있습니다.

결론

이 튜토리얼에서는 C++를 사용하여 약수의 개수가 n을 초과하는 첫 번째 삼각수를 찾는 방법을 배웠습니다. 삼각수 판별 함수와 약수 개수 계산 함수를 조합하여 문제를 해결했습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.