Skip to content

Latest commit

 

History

History
44 lines (33 loc) · 1.17 KB

풀이_LC441.md

File metadata and controls

44 lines (33 loc) · 1.17 KB

💰 LeetCode 441. Arranging Coins

  • Date : 2021.06.20(일)
  • Time : 15분

Problem

  • You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.
  • Given the integer n, return the number of complete rows of the staircase you will build.

Constraints

  • 1 <= n <= 2^31 - 1

Example

  • Input: n = 8
  • Output: 3
  • Explanation: Because the 4th row is incomplete, we return 3.



풀이

class Solution:
    def arrangeCoins(self, n: int) -> int:
        if n == 1: return n

        left = 0
        right = n

        ans = 0

        while (left <= right):
            mid = (left+right) // 2
            sum = mid*(mid+1) // 2
            if (sum <= n):
                ans = mid
                left = mid + 1
            else :
                right = mid - 1
                
        return ans

: 등차수열을 이용해 풀었다. 이 문제에서 코인의 열은 1,2,3으로 등차수열로 +1씩 들어나기 때문이다. left와 right를 준 후 중간값을 구하고, 그 값으로 등차수열을 실행하였다.