[알고리즘] 백준 > #6236. 용돈 관리

문제링크

백준 #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;
    }
}