JAVA / Lv 0. Arranging Coins
문제
당신은 동전을 n개 가지고 있고 이 동전으로 계단을 만들고 싶어합니다. 계단은 k행으로 구성되어 있으며 행에는 정확히 동전이 있습니다. 계단의 마지막 행은 불완전 할 수 있습니다.
정수가 주어지면 n, 만들 계단의 완전한 행의 수를 반환합니다 .
제한사항
- 1 <= n <= 231 - 1
입출력 예
문제 해결
중간행을 구하고
(left + right) / 2;
중간행까지 더합니다. (등차수열)
(long) mid * (mid + 1) / 2;
더한 값이 n보다 작거나 같으면 즉, 주어진 동전보다 작거나 같게 사용해서 하나의 행을 완성시켰습니다.
그렇다면 그 행을 answer에 update 시키고 더 큰 수를 찾으러 떠나기 위해 다음 행으로 +1 해줍니다.
반면, 주어진 동전보다 많게 사용하려하면 mid값이 크다는 의미이므로 mid - 1 해줍니다.
해당 조건들을 계속 반복하다보면 왼쪽 오른쪽의 폭이 점점 줄어들고 left, right가 같아진다면
로직은 종료가 됩니다.
나의 풀이
class Solution {
public int arrangeCoins(int n) {
int left = 0, right = n;
int answer = 0;
while(left <= right){
int mid = (left + right) / 2;
long k = (long) mid * (mid + 1) / 2;
if(k <= n){
answer = mid;
left = mid + 1;
}else{
right = mid - 1;
}
}
return answer;
}
}
'TIL' 카테고리의 다른 글
99클럽 코테 스터디 34일차 TIL (BFS) (0) | 2024.08.24 |
---|---|
99클럽 코테 스터디 33일차 TIL (0) | 2024.08.24 |
99클럽 코테 스터디 29일차 TIL (이분탐색) (1) | 2024.08.19 |
99클럽 코테 스터디 28일차 TIL (우선순위 큐) (0) | 2024.08.19 |
99클럽 코테 스터디 27일차 TIL (구현) (0) | 2024.08.19 |