[LeetCode/리트코드]#441: Arranging Coins[python/파이썬/이분탐색/수학]

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

Arranging Coins - LeetCode

1+2+3...+k = k(k+1)/2 라는 공식이 있다. 

이를 이용하여 이분탐색이나 수학 알고리즘으로 구현할 수 있다. 

접근법 1) 이분탐색 _Binary Search

시간복잡도 O(log N)

 

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        stair=0
        i=0
        while 1:
            i+=1
            stair+=i
            if stair >= n:
                row=i
                break
        if stair>n:
            row-=1
        return row

 

접근법 2) 수학 _Math

시간복잡도 O(1)