[JAVA]백준 6236: 용돈 관리

백준 6236: 용돈 관리

Link: https://www.acmicpc.net/problem/6236

풀이

• 이분탐색이 너무 머리에 안들어와서 분류를 알고 푼 문제
• 인출 횟수를 기준으로 이분탐색
• 범위를 제대로 못 잡아서 계속 틀렸음.

package algorithm2024.jan.day03;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_6236_용돈관리 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] cost = new int[N];
        int max = 0;
        for (int i = 0; i < N; i++) {
            cost[i] = Integer.parseInt(br.readLine());
            max = Math.max(max,cost[i]);
        }
        int lo = max;
        int hi = 2_000_000_000;

        while(lo<hi){
            int mid = (lo+hi)/2;
            int cnt = 0;
            int cur = 0;
            for (int i = 0; i < N; i++) {
                cur-=cost[i];
                if(cur<0){
                    cnt++;
                    cur = mid-cost[i];
                }
            }
//            System.out.println(lo+" "+hi+" "+mid+" "+cnt);
            if(cnt>M){
                lo = mid+1;
            }else{
                hi = mid;
            }
        }
        System.out.println(lo);
    }
}

---

Issue

• 이분탐색은 왜 이리 어려울까 2트