[leetcode][441] Arranging Coins

문제 : https://leetcode.com/problems/arranging-coins/

---

n 개의 동전이 있으면 이를 계단 모양으로 배열하려고 한다.

i번째 계단에는 i개의 동전이 있어야 한다. 

n개의 동전으로 조건을 충족시키는 계단의 최대 행 수를 구하라.

---

1부터 1씩 증가시키면서 i번째 행의 계단을 만들 때 필요한 동전 수를 구해서 정답을 구할수도 있다.

이렇게 풀면 O(N)으로 문제를 해결할 수 있을 것이다. 

더 빠른 방법을 알아보자.

 

계단은 등차 수열이니까 i개의 행을 가진 계단을 만들고자 할 때 등차수열의 합 공식( i * (i + 1) / 2 )을 이용하면 필요한 동전 수를 O(1)만에 구할 수 있다.

이를 이용해서 parametric search 방식으로 문제를 다시 생각해보자.

i 행의 계단을 만들 때 n개의 동전으로 만들 수 있는지 판단한다.

가능한 i의 범위는 1~n 이다. (n이 0이면 정답은 0이 되겠지만 예외처리가 약간 귀찮아지므로 초반에 n이 0이면 0을 반환하게 예외처리해준다.)

즉, l = 1, r = n. 일 때 그 중간 값 m을 위에서 설명한 i라 하고 m 행의 계단을 만들 때 필요한 동전 수를 계산한다. 결과 값이 n보다 작거나 같다면 가능한 경우다. 이 때 정답을 갱신한다.

우리가 구하고자 하는 건 만들 수 있는 계단의 최대 행 수이므로 m 행의 계단을 만들 수 있다면 l을 m+1로 갱신한다. m 행의 계단을 n개의 동전으로 만들 수 없다면 r을 m-1로 갱신한다.

l이 r보다 작거나 같을 때 위 로직을 반복한다.

 

이렇게 이분탐색을 사용하면 시간복잡도 O(logN)만에 풀 수 있다.

---

소스코드

https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/441.%20Arranging%20Coins.cpp

https://github.com/fpdjsns/Algorithm-python/blob/main/leetcode/easy/441.%20Arranging%20Coins.py

---

 

좋아. 점점 이분탐색으로 해결방법을 생각하는데 익숙해지고 있다. 아~주 좋아.