C/C++로 구현하는 삼각형 성냥개비 수(Triangular Matchstick Number) 계산 프로그램

성냥개비를 배열하여 정삼각형을 만들 때 필요한 성냥개비의 개수를 삼각형 성냥개비 수(Triangular Matchstick Number)라고 합니다. 즉, 특정 층수의 성냥개비 피라미드를 완성하는 데 필요한 최소 성냥개비 개수를 의미합니다.

문제 정의

이 문제에서는 성냥개비 피라미드의 바닥층 크기 X가 주어집니다. 우리의 목표는 X개의 층으로 이루어진 성냥개비 피라미드를 만들 때 필요한 총 성냥개비의 최소 개수를 출력하는 프로그램을 작성하는 것입니다.

예시를 통해 개념을 더 명확하게 이해해 보겠습니다.

입력: 7
출력: 84

풀이 접근 방식

이 문제는 삼각수(Triangular Number)의 확장 개념입니다. 삼각수란 1부터 n까지의 자연수의 합, 즉 n*(n+1)/2로 표현되는 수입니다.

정수 X가 주어졌을 때, 각 층은 하나의 삼각형을 이루며 각 삼각형은 세 변으로 구성되므로, 필요한 성냥개비의 개수는 X번째 삼각수의 3배가 됩니다. 따라서 공식은 다음과 같습니다.

필요한 성냥개비 수 = (3 × X × (X + 1)) / 2

X = 7인 경우, (3 × 7 × 8) / 2 = 168 / 2 = 84가 되어 예상 출력과 일치합니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int main() {
    int x = 7;
    cout << (3 * x * (x + 1)) / 2;
    return 0;
}

출력 결과

84

복잡도 분석

이 알고리즘은 단순한 산술 공식을 사용하므로 시간 복잡도는 O(1), 공간 복잡도 역시 O(1)입니다. 입력 크기와 무관하게 상수 시간에 결과를 계산할 수 있어 매우 효율적입니다. 다만 X가 매우 클 경우 정수 오버플로우를 방지하기 위해 long long 타입을 사용하는 것이 좋습니다.