C++로 구현하는 배열 값 기반 삼각형 피라미드의 최대 높이 알고리즘

문제 개요

주어진 배열의 값들을 이용해 삼각형(피라미드) 형태를 만들 때, 만들 수 있는 최대 높이를 구하는 문제입니다. 단, 피라미드의 각 레벨은 아래에서 위로 올라갈수록 더 적은 수의 원소로 구성되며, 상위 레벨의 합은 하위 레벨보다 커야 한다는 조건을 만족해야 합니다.

예시

입력 배열이 {40, 100, 20, 30}이라고 가정해 보겠습니다. 이 경우 정답은 2가 됩니다.

그 이유는 맨 아래 층에 100과 20을 배치하고, 그 위 층에는 40 또는 30 중 하나를 배치할 수 있기 때문입니다. 즉, 두 층으로 이루어진 피라미드를 완성할 수 있습니다.

접근 방식 및 알고리즘

이 문제의 해결 핵심은 등차수열의 합 공식에 있습니다. 높이가 h인 삼각형 피라미드를 완성하려면 최소한 다음과 같은 개수의 원소가 필요합니다.

필요한 원소의 개수 = h × (h + 1) / 2

따라서 배열의 크기 n이 주어졌을 때, h × (h + 1) / 2 ≤ n을 만족하는 가장 큰 h를 찾으면 그것이 곧 피라미드의 최대 높이가 됩니다. 이 조건을 순차적으로 검사하면서 조건을 벗어나는 시점에 반복을 종료하면 됩니다.

C++ 구현 코드

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

int getMaximumHeight(int *arr, int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        long long y = (i * (i + 1)) / 2;
        if (y < n) {
            result = i;
        } else {
            break;
        }
    }
    return result;
}

int main() {
    int arr[] = {40, 100, 20, 30};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Result = " << getMaximumHeight(arr, n) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.

Result = 2

복잡도 분석

이 알고리즘은 높이 후보 값을 하나씩 증가시키며 검사하므로, 시간 복잡도는 O(√n) 수준입니다. 이는 h × (h + 1) / 2 ≈ n이 되는 지점에서 반복이 종료되기 때문입니다. 공간 복잡도는 추가 자료구조를 사용하지 않으므로 O(1)로 매우 효율적입니다.