동전으로 만들 수 있는 최대 높이의 피라미드를 구하는 C++ 프로그램

n개의 동전이 주어졌을 때, 이 동전들을 활용하여 최대 높이의 피라미드를 만들어야 합니다. 첫 번째 동전은 첫 번째 줄에, 두 번째와 세 번째 동전은 두 번째 줄에 배치하는 식으로, 아래층부터 한 줄씩 동전 수를 늘려가며 쌓아 올립니다.

예를 들어 6개의 동전으로는 높이 3의 피라미드를 만들 수 있습니다. 높이 4의 피라미드를 완성하려면 총 10개의 동전이 필요하기 때문에, 6개로는 그 이상 쌓을 수 없습니다.

피라미드 높이 계산 공식

피라미드의 높이는 다음 공식을 사용하면 간단하게 구할 수 있습니다.

H = {(-1 + √(1+8N)) / 2}

입력: n = 10
출력: 피라미드의 높이: 4

설명

위 공식에 n = 10을 대입하면 다음과 같이 계산됩니다.

H = (-1 + √(1 + 8 × 10)) / 2 = (-1 + √81) / 2 = (-1 + 9) / 2 = 4

따라서 10개의 동전으로 만들 수 있는 피라미드의 최대 높이는 4입니다. 이 공식은 1부터 h까지의 합(h(h+1)/2)이 전체 동전 개수 N보다 작거나 같은 최댓값 h를 찾는 원리를 근거로 하며, 정수 나눗셈을 활용해 소수점 이하를 자동으로 버림 처리합니다.

예제 코드

#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int n = 10;
    int height = (-1 + sqrt(1 + 8 * n)) / 2;
    cout << "피라미드의 높이: " << height;
}