[LeetCode] 441.Arranging Coins | LIM

문제

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

Arranging Coins - LeetCode

 

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 staricase you will build

 

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

 

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

 

설명

위에서부터 코인을 1, 2, 3, 4... 순차적으로 한 개씩 늘려가면서 채우는데 총 내가 가지고 있는 coin으로 몇 번째 칸까지 채울 수 있을 것인가에 대한 문제이다.

 

가장 간단하게 생각하면 1 + 2 + 3 + 4... 를 하다가 합이 n 보다 커지는 순간 그 전에 숫자를 return 하면 된다. 

하지만 이렇게 되면 문제 조건에 따라 시간초과가 발생하게 된다.

Constraints:
1 <= n <= 2**31 - 1

 

푼 방법

식을 쓰다보니 이차방정식 근을 구하는 문제였다. 식은 다음과 같다.

 

코드

class Solution:
    def arrangeCoins(self, n: int) -> int:
        return int(((8*n+1) ** (1/2) - 1) / 2)

 

위에서 보이는 식 중 왼쪽 마지막 부분을 그대로 코드에 옮겨 적었다. 

 

결과는 다음과 같다.