[LeetCode] Arranging Coins 파이썬 (Binary Search, maximize)

class Solution2(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left <= right:
            mid = left + (right - left) / 2
            if 2 * n < mid * (mid+1):
                right = mid - 1
            else:
                left = mid + 1
        return left - 1

class Solution:
    def arrangeCoins(self, n: int) -> int:
        left, right = 0, n
        while left <= right:
            mid = (left+right) // 2
            coins = (mid*(mid+1))//2
            if coins == n:
                return mid
            elif coins > n:
                right = mid - 1
            else:
                left = mid + 1
        return right # need maximum value

문제를 직사각형으로 확장하면 쉽게 풀리지만 그걸 떠올리기가 쉬운지는 모르겠음.

 

높이(k)가 3일 경우,

o x x

o o x

o o o

이런식으로 만들어 진다.

여기에 1열을 추가한다면

o x x x

o o x x

o o o x

이렇게 k * k+1의 직사각형의 면적의 절반이 n개의 코인을 위치시킬 수 있는 최대 값이다.

 

k * (k+1) / 2 <= n 이 충족되는 k의 최대 값(right pointer)이 문제에서 찾고자 하는 row의 number가 되는 것이다.

 

 

 

 

 

Why Binary Search in this problem?

www.youtube.com/watch?v=vPvnYNjqSh0

출처: github.com/jiapengwen/LeetCode/blob/master/Python/arranging-coins.py