이진탐색 문제 해결 - 백준 용돈 관리

문제

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

 

- 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 

- 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다.

- 현우는 통장에서 K원을 인출하며, 

통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다.

- 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 

남은 금액이 그날 사용할 금액보다 많더라도, 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다.

- 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 

- 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

 

입력

- 1번째 줄에는 N과 M이 공백으로 주어진다. (1<=N<=100,000, 1<=M<=N)

- 2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1<=금액<=10000)

 

출력

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

 

참고-1.

https://velog.io/@ilil1/%EB%B0%B1%EC%A4%80-6236%EB%B2%88-%EC%9A%A9%EB%8F%88-%EA%B4%80%EB%A6%AC-java 

 

문제 해석

- 현우가 1 <= N <= 100,000일 동안 사용할 돈이 미리 주어졌을 때, 정확히 M번 출금하여 먹고 살 수 있도록 하는 가장 작은 K를 구하는 문제

- 만약 인출액 K가 매우 크다면 단 한번의 출금만으로도 N일 동안 돈을 사용할 수 있을 것이다.

- 만약 인출액 K가 작다면 출금을 더 자주 해야 할 것이다. 따라서 K와 출금 횟수는 반비례

 

문제 풀이

import java.util.Scanner;

public class Main {
	static int N, M;
	static int[] arr;
	static int max = 0;
	static int result;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // 돈을 사용할 일수
		M = sc.nextInt(); // 출금 횟수
		arr = new int[N];

		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
			max = Integer.max(max, arr[i]);
		}
		// 돈을 가장 많이 쓰는 날 이상의 금액을 인출해야 한다.
		// 그렇지 않으면 인출을 하더라도 금액이 부족하기 때문에 계속 인출을 반복하게 된다.
		int left = max;
		int right = 10_000 * 100_000;
		int count = 0;
		// 이진 탐색을 이용하여 해답을 찾는다.