6236_용돈 관리

사용 알고리즘:  이분 탐색

사용 언어: java

 

package ssafyRoom2_Monthly_Silver_Random_Defense;

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int l = 0;
		int r = 10000 * n;
		
		int[] day = new int[n];
		for (int i = 0; i < n; i++) {
			day[i] = sc.nextInt();
			l = Math.max(l, day[i]);
		}
		
		//
		while(l <= r) {
			int mid = (l + r) / 2;
			if(solve(mid, day, r) <= m) {
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		System.out.println(l);
	}

	private static int solve(int mid, int[] day, int r) {
		int cnt = 0;
		int sum = r;
		for (int i = 0; i < day.length; i++) {
			sum += day[i];
			if(sum > mid) {
				cnt++;
				sum = day[i];
			}
		}
		return cnt;
	}

}

 

문제 이해하기가 어렵...

한 번 인출하면, 돈이 부족하기 전까지는 인출된 돈을 계속 가지고 있으면서 쓸 수 있다.