C++로 동전 계단 배열 문제 해결하기

문제 설명

n개의 동전이 주어지고, 이를 계단 모양으로 배치하려고 합니다. 이때 k번째 행에는 반드시 정확히 k개의 동전이 놓여야 합니다. 따라서 동전의 총 개수 n이 주어졌을 때, 만들 수 있는 완전한 계단 행의 개수를 구하는 것이 목표입니다.

예를 들어 입력이 5라면 출력은 2가 됩니다. 5개의 동전으로는 두 개의 완전한 계단 행을 만들 수 있지만, 세 번째 행을 완성하려면 3개가 더 필요한데 동전은 2개만 남기 때문입니다 −

*
**
**

해결 접근 방식

이 문제는 수학적 공식을 사용하면 반복문 없이 O(1) 시간 복잡도로 바로 해결할 수 있습니다. 1부터 k까지의 합이 k(k+1)/2임을 이용하면, 다음 공식으로 완전한 행의 개수를 구할 수 있습니다 −

$$\frac{\sqrt{(8n+1)}-1}{2}$$

즉, 8n+1에 제곱근을 취한 값에서 1을 빼고 2로 나눈 뒤 소수점 이하를 버리면 답이 됩니다. 이때 큰 수의 오버플로우를 방지하기 위해 n을 long long 타입으로 변환하여 계산하는 것이 안전합니다.

예제 코드

아래 C++ 구현 예시를 통해 더 자세히 이해해 보겠습니다 −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int arrangeCoins(int n) {
      return (sqrt(8*(long long)n+1)-1)/2;
   }
};
main(){
   Solution ob;
   cout << (ob.arrangeCoins(13));
}

입력

13

출력

4

위 예제에서 13개의 동전은 1+2+3+4 = 10개로 네 개의 완전한 행을 만들 수 있으며, 남은 3개로는 다섯 번째 행(5개 필요)을 채울 수 없으므로 결과는 4가 됩니다.