[백준 6236번] 용돈 관리 (java)

6236번: 용돈 관리

이분탐색으로 문제를 풀었다.

이분탐색의 먼저 범위(left ~ right)를 정해야 한다. 

 

left : 현우가 N번 동안 필요한 금액 중 최대값이 이분탐색 범위의 시작값이 되어야 한다.       

       예를 들어 현우가 n번째에 500원이 필요한데, 한 번에 인출할 수 있는 금액이 500원보다 작은 400원

       이라면 현우는 n번째에 돈을 쓸 수가 없다.

 

right : 현우가 N번 동안 필요한 금액의 총 합이 이분탐색 범위의 끝값이 된다.

 

 

이분탐색을 진행하면서 현우가 통장에서 인출해야할 최소 금액 K를 찾는다.

 

소스코드 : 

	import java.io.*;
	public class n06236 {
	static int N, M;
	static int[] arr;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String[] sarr = br.readLine().split(" ");
	N = Integer.parseInt(sarr[0]);
	M = Integer.parseInt(sarr[1]);
	arr = new int[N];
	int max = 0;
	int sum = 0;
	for (int i = 0; i < N; i++) {
	arr[i] = Integer.parseInt(br.readLine());
	max = Math.max(max, arr[i]);
	sum += arr[i];
	}
	bw.write(binSearch(max, sum) + "\n");
	bw.flush();
	}
	public static int binSearch(int left, int right) {
	int pl = left;
	int pr = right;
	do {
	int pc = (pl + pr) / 2;
	int cnt = 1;
	int money = pc;
	for (int i = 0; i < N; i++) {
	if (arr[i] > money) {
	money = pc;
	cnt++;
	}
	money = money - arr[i];
	}
	if (cnt > M)
	pl = pc + 1;
	else
	pr = pc - 1;
	} while (pl <= pr);
	return pl;
	}
	}

view raw 6236.java hosted with ❤ by GitHub