[백준/Java] 6236 용돈 관리

조건

1. N은 돈을 사용할 일 수를 받는다. (1<= N <= 100,000 , Int)

2. M은 몇 번을 돈을 인출할 것인가이다. (1<= M <= N , Int)

3. 여기서 현우가 정확히 M번을 맞추기 위해 남은 금액이 그날 사용 금액보다 많더라도 남은 금액은 통장에 집어넣을 수있다라고 했기에 count를 조건을 이하로 설정하면 된다. (M번 보다 적게 되더라도 조건이 충족한다면 입출금을 남은 횟수만큼 하면 되기 때문이다.)

4. 돈을 인출할 때 최소 인출금액을 사용할 금액의 최대의 수로 지정한다.

예제 입력

코드

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;
		}
	}
}