[伯俊/Java]6236小遣い管理

条件

入力例

コード#コード#

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



public class Main {
	
	static int N,M;
	static int[] A;
	
	
	static FastReader scan = new FastReader();
	static StringBuilder sb = new StringBuilder();

	static void input() {
		N = scan.nextInt(); // 용돈 사용날의 수를 받는다.
		M = scan.nextInt(); // 인출 횟수를 받는다.
		A = new int[N + 1]; //index를 1부터 시작하기 위해 +1을 해준다.
		for(int i =1;i<=N;i++){
			A[i] = scan.nextInt();
		}
	}

	
	static boolean findAns(int K) {
		int sum =0 , cnt = 1; // 
		for(int j = 1;j<=N;j++) {
			if(sum + A[j] > K){ // 돈이 부족하다면 
				cnt ++;  // 출금횟수를 +1해주고
				sum = A[j]; // sum에 대입
			} else {
				sum += A[j]; 출금금액에서 돈이 남는다면 그냥 sum에다가 더해주기만한다.
			}
		}
		return cnt <= M; // 총 출금의 횟수가 이하인지 확인
	}
	

	static void find() {
		int L = A[1], R = 1000000000, ans =0; 
		for(int i= 1;i<=N;i++) {
			L = Math.max(L, A[i]); // 최소 출금 금액을 사용할 금액의 최대값으로 해준								   // 다.
		}
		while(L<=R) {
			int mid = (L + R) / 2;
			if(findAns(mid)) {
				ans = mid;
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}
		System.out.println(ans);
		}

		
		
	public static void main(String[] args) {
		input();
		find();
	}
	
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}
		
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		Long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			}catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}