[LeetCode] 441. Arranging Coins

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

Arranging Coins - LeetCode

Arranging Coins - Easy

 

주어진 동전을 1,2,3,4,... 이렇게 계단식으로 쌓아내려갈때 꽉 채워진 층수를 구하는 문제이다.

그림만 보고 이해를 잘못하여 위에서부터가 아닌 왼쪽부터 채워지는 줄 알고 삽질을 좀 했다..

1,2,3,4,... 이런식으로 동전이 쌓인다면, k층 까지 쌓인 동전의 개수는 k*(k+1)/2 가 된다. (가우스 계산)

따라서 이 수가 n 이상이 될때의 k를 찾아주자.

n과 같아진다면, 모든 층이 꽉 찬 상태이므로 k를 리턴해주면 되고, n보다 커진다면 마지막층은 채워지지 않았으므로 k-1을 리턴하자.

 

전체 풀이 코드

class Solution {
public:
    int arrangeCoins(int n) {
        long k=0;
        for (;k*(k+1)/2 < n; k++);
        return k*(k+1)/2==n?k:k-1;
    }
};