예제: Arranging Coins
문제
You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.Given n, find the total number of full staircase rows that can be formed.
n is a non-negative integer and fits within the range of a 32-bit signed integer.
Example 1:n = 5 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ Because the 3rd row is incomplete, we return 2.Example 2:
n = 8 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ Because the 4th row is incomplete, we return 3.
풀이
주어진 수로 만들 수 있는 계단의 최대 높이를 구하는 문제이다.
CASE1은 단순히 1, 2, 3... 씩 차감하며 답을 찾는 간단한 로직이다.
CASE2는 무려 수학 공식을 사용한다.
아래에는 필자가 사용했던 수학공식을 늘어놓으려 한다.
nk번째의 식을 구하기 위하여 아래와 같이 식을 세운다.
n2 = n1 + 2
n3 = n2 + 3
.
.
.
nk = n(k-1) + k이리하여, 정리하면 다음과 같다.
nk = n1 + (2 + 3 + ... + k)
n1 = 1이므로, 결국 nk = 1부터 k까지의 합 이다.
1부터 k까지의 합 = k(k+1)/2 이고, 이 수는 주어진 수 n보다 작거나 같다.
즉, k(k+1)/2 <= n 이다.
k를 구하기 위하여 아래와 같이 구한다.
k^2 + k <= 2n
k^2 + k + 1/4 <= 2n + 1/4
(k + 1/2)^2 <= 2n + 1/4
k + 1/2 <= sqrt(2n + 1/4)
k <= sqrt(2n + 1/4) - 1/2자, 다 구했다. 이를 자료형에 유의하여 return하면 되고, 그 식은 CASE2를 참고해주시라.
전체적인 소스코드는 아래와 같다.
소스 코드
/* CASE1 */
class Solution {
public:
int arrangeCoins(int n) {
int i = 1;
while (n >= 0) {
n -= i;
i++;
}
return i - 2;
}
};
/* CASE2 */
class Solution {
public:
int arrangeCoins(int n) {
return (sqrt(2.0 * n + 0.25) - 0.5);
}
};풀이 후기
오랜만에 고등학교 수학같은걸 풀었더니 재미있다.
대학교때 필자는 수학을 참으로 좋아했는데, 고등학교때까지는 내가 수학을 좋아한다는 것을 몰랐다. 알았다면, 수학과는 아니더라도 수학과 밀접한 관련이 있는 학문을 공부하지 않았을까.. 생각한다. 뭐, 그것도 일로 한다면 재미없어질 수 있겠지만.
