[BOJ][6236] 용돈관리 - JAVA

- 링크 : https://www.acmicpc.net/problem/6236

6236번: 용돈 관리

 

- 풀이

 - 이분 탐색 문제 (풀이 보고 품 링크 : https://maivve.tistory.com/150)

 - 현재 이분 탐색 문제라고 판단하는 기준이 부족하다는 것을 느낌

 : 현재까지 생각 해 볼 것 (1번 해볼만한 범위(이번 문제는 가장 큰 수가 10억), 고정된 숫자 미리 제공, 답이 카운트와 연결)

 

 

 

import java.util.*;

public class Solution {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] costs = new int[n];
        int maxVal = 0;

        for (int i = 0; i < n; i++) {
            costs[i] = sc.nextInt();
            maxVal = Math.max(maxVal, costs[i]);
        }

        int left = maxVal;
        int right = maxVal * m;

        while(left <= right) {
            int mid = (left + right) / 2;
            int current = mid;
            int count = 0;
            for(int cost: costs) {
                if(cost > current) {
                    count++;
                    current = mid - cost;
                } else {
                    current -= cost;
                }
            }

            if (current > 0) {
                count++;
            }

            if (count <= m) {
                right = mid-1;
            } else {
                left = mid+1;
            }

        }

        System.out.println(left);


    }
}