이번 글에서는 흥미로운 알고리즘 문제를 하나 살펴보겠습니다. N개의 동전이 주어졌을 때, 이 동전들을 피라미드(삼각형) 형태로 쌓을 수 있는 최대 높이를 구하는 것이 목표입니다. 여기서 피라미드는 첫 번째 층에 동전 1개, 두 번째 층에 동전 2개, 세 번째 층에 동전 3개와 같은 방식으로 층마다 하나씩 동전이 늘어나는 구조입니다.
위 그림에서 볼 수 있듯이, 높이 3짜리 피라미드를 만들려면 최소 6개의 동전(1+2+3=6)이 필요합니다. 마찬가지로 높이 4짜리 피라미드를 완성하려면 10개의 동전(1+2+3+4=10)이 있어야 합니다. 동전이 9개뿐이라면 높이 4는 만들 수 없습니다.
그렇다면 주어진 동전 개수로 쌓을 수 있는 최대 높이는 어떻게 빠르게 계산할 수 있을까요?
수학적 접근 방법
높이 h짜리 피라미드를 만들려면 1부터 h까지의 합, 즉 h(h+1)/2개의 동전이 필요합니다. 따라서 n개의 동전으로 만들 수 있는 최대 높이는 다음 공식으로 한 번에 계산할 수 있습니다.
h = (-1 + √(1 + 8n)) / 2
이 공식은 n = h(h+1)/2라는 이차방정식을 h에 대해 풀어서 유도한 것입니다. 제곱근 연산 결과는 실수이므로, 정수형 변수에 저장하는 과정에서 자동으로 소수점 이하가 버려져(내림 처리) 올바른 최대 높이를 얻게 됩니다.
예제 코드
#include<iostream>
#include<cmath>
using namespace std;
int getMaxHeight(int n) {
int height = (-1 + sqrt(1 + 8 * n)) / 2;
return height;
}
main() {
int N;
cout << "Enter number of coins: ";
cin >> N;
cout << "Height of pyramid: " << getMaxHeight(N);
}
실행 결과
Enter number of coins: 13
Height of pyramid: 4
동작 원리 살펴보기
동전이 13개일 때를 예로 들어보겠습니다. 공식에 대입하면 (-1 + √(1 + 8×13)) / 2 = (-1 + √105) / 2 ≈ 4.62가 되고, 정수 부분인 4가 최대 높이입니다. 실제로 1+2+3+4=10개의 동전으로 높이 4의 피라미드를 완성할 수 있으며, 남은 3개의 동전으로는 5개가 필요한 다섯 번째 층을 채울 수 없습니다.
이 방법의 가장 큰 장점은 시간 복잡도가 O(1)이라는 점입니다. 동전 개수가 아무리 많아도 반복문 없이 단 한 번의 계산으로 답을 구할 수 있습니다. 반면, 층을 하나씩 더해가며 확인하는 단순 반복 방식은 O(√n)의 시간이 걸리므로, 위의 공식 기반 접근이 훨씬 효율적입니다.