[알고리즘] 백준 > #6236. 용돈 관리
문제링크
풀이방법
이분탐색 문제였다. 왼쪽값(start)는 k가 될 수 없는 수 중 가장 큰 수로 계속 갱신해 나가고 오른쪽값(end)는 최소 k로 계속 갱신해 나갔다. 문제에 1 ≤ 금액 ≤ 10000
이렇게 되어있어서 처음에 end를 10000로 설정했는데 N이 최대 100,000이기 때문에 이를 꼭 고려해줘야한다! 그리고 if ((balance -= spending[i]) < 0) return false; 이부분도 꼭 고려해줘야하는 부분이다.
코드
class Solution6236 {
int n, m;
int[] spending;
Solution6236(int n, int m, int[] spending) {
this.n = n;
this.m = m;
this.spending = spending;
}
int getMinK() {
int start = 0;
int end = 10000 * 100000;
while ((end - start) > 1) {
int mid = (start + end) / 2;
if (isPossibleK(mid)) end = mid;
else start = mid;
}
return end;
}
private boolean isPossibleK(int k) {
int count = 0;
int balance = 0;
for (int i = 0; i < n; i++) {
if (balance < spending[i]) {
balance = k;
count++;
if (count > m) return false;
}
if ((balance -= spending[i]) < 0) return false;
}
return true;
}
}
Author And Source
이 문제에 관하여([알고리즘] 백준 > #6236. 용돈 관리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cchloe2311/알고리즘-백준-6236.-용돈-관리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)