이 글에서는 아래의 문제 상황에 대한 해결 방법을 단계별로 살펴보겠습니다.
문제 정의
문제 — N개의 동전이 주어졌을 때, 이를 삼각형 형태로 배열해야 합니다. 즉, 첫 번째 행에는 동전 1개, 두 번째 행에는 동전 2개, 세 번째 행에는 동전 3개를 배치하는 방식입니다. 이때 N개의 동전으로 만들 수 있는 삼각형의 최대 높이를 구하는 것이 목표입니다.
예를 들어 동전이 17개라면 1 + 2 + 3 + 4 + 5 = 15개로 높이 5까지 쌓을 수 있고, 남은 2개로는 여섯 번째 행을 완성할 수 없으므로 최대 높이는 5가 됩니다.
접근 방법
높이가 h인 삼각형을 완성하려면 1 + 2 + … + h = h(h+1)/2 개의 동전이 필요합니다. 따라서 h(h+1)/2 ≤ N을 만족하는 가장 큰 정수 h를 찾으면 되며, 이차방정식을 풀면 다음과 같은 공식이 도출됩니다.
h = (−1 + √(1 + 8N)) / 2
여기서는 바빌로니아 법(뉴턴 방법)을 이용해 제곱근을 직접 계산한 뒤, 위 공식에 대입하여 최대 높이를 구합니다.
구현 예제
# squareroot
def squareRoot(n):
# initial approximation
x = n
y = 1
e = 0.000001 # allowed error
while (x - y > e):
x = (x + y) / 2
y = n/x
return x
# max height
def find(N):
# calculating portion of the square root
n = 1 + 8*N
maxH = (-1 + squareRoot(n)) / 2
return int(maxH)
# main
N = 17
print("Maximum height is :",find(N))
출력 결과
Maximum height is : 5
코드 설명
- squareRoot(n): 초기 근사값 x = n, y = 1에서 시작하여 두 값의 차이가 허용 오차(e = 0.000001) 이하가 될 때까지 평균값을 반복 계산함으로써 제곱근을 구합니다.
- find(N): 판별식에 해당하는 1 + 8N을 계산한 뒤, 공식 (−1 + √n) / 2에 대입하고 정수 부분만 잘라내어 최대 높이를 반환합니다.
- 모든 변수는 지역 범위(local scope) 내에서 선언되므로 함수 외부에 영향을 주지 않습니다.
결론
이 글에서는 동전을 삼각형 형태로 배열할 때 만들 수 있는 최대 높이를 구하는 파이썬 프로그램 작성 방법을 알아보았습니다. 등차수열의 합 공식과 반복 연산을 통한 제곱근 계산을 결합하면, 복잡한 반복문 없이도 O(log N) 수준의 효율로 답을 구할 수 있습니다. 이 접근 방식은 계단 쌓기, 층별 배치 등 유사한 수학적 문제에도 응용할 수 있습니다.