BOJ6236 용돈관리 (매개변수 탐색)

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

6236번: 용돈 관리

 

import java.util.*;
import java.io.*;

public class Main
{
    
    public static long[] money;
    public static int n;
    public static int m;
    
    public static boolean checkPossible(long cash){
        int count=1;
        long mo=cash;
        for(int i=0; i<n;i++){
            if(count>m) return false;
            
            if (mo<money[i]){
                mo = cash;
                mo -= money[i];
                if(mo<0){
                    return false;
                }
                count++;
            }else{
                mo -= money[i];
            }
        }
        if(count<=m) {
            return true;
        }else{
            return false;
        }
    }
    
    public static long search(){
        long l = 0l;
        long r = 1l<<32 -1 ;
        long ans = 0;
        while(l<=r){
            long mid = (l+r)/2;
        
            
            if(checkPossible(mid)){
                r=mid-1;
                ans=mid;
                
            }else{
                l=mid+1;
                
            }
            
        }
        
        return ans;
    }
    
    
    
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    String[] input1 = br.readLine().split(" ");
	    
	    n = Integer.valueOf(input1[0]);
	    m = Integer.valueOf(input1[1]);
		money = new long[n];
		
		for(int i=0; i<n;i++){
		    money[i] = Long.valueOf(br.readLine());
		}
		
		long ans = search();
		
		System.out.println(ans);
		
		
		
		
	}
}

import java.util.Scanner;

class Main
{
    static boolean isPossible(int[] useAmounts, int drawAmount, int maxDrawCount) {
        int drawCount = 1;
        int currentAmount = drawAmount;
        for (int useAmount : useAmounts) {
            if (useAmount > drawAmount) return false;
            if (currentAmount < useAmount) {
                if (drawCount == maxDrawCount) return false;
                drawCount++;
                currentAmount = drawAmount;
            }
            currentAmount -= useAmount;
        }
        return true;
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] useAmounts = new int[N];
        for (int i = 0; i < N; i++)
            useAmounts[i] = sc.nextInt();

        int l = 1, r = N * 10000, ans = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (isPossible(useAmounts, m, M)) {
                ans = m;
                r = m - 1;
            }
            else l = m + 1;
        }
        System.out.println(ans);
    }
}