백준 2343번 : 기타 레슨(Java)

 

2343번: 기타 레슨

---

[풀이]

 

- 이분탐색 유형의 문제입니다.
- 최적의 크기를 구해야 하므로 mid 변수를 기준으로 계산을 합니다.
- solve 메소드 내부의 for 반복문에서 합이 mid보다 커질 경우, count 변수에 1을 더합니다.
- 마지막에 count 변수가 m 이하일 경우, end변수에 mid - 1 값을 할당합니다.
- while 반복문이 끝난다면, start 변수를 반환합니다. (사실, mid 변수를 다른 곳에 선언해서 mid를 반환해도 됩니다.)

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int n, m;
	static int[] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[n];

		st = new StringTokenizer(br.readLine(), " ");
		int maxValue = 0;
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			maxValue = Math.max(maxValue, arr[i]);
		}
		System.out.println(solve(maxValue, Integer.MAX_VALUE));
	}

	public static long solve(long start, long end) {
		while (start <= end) {
			long sum = 0;
			long mid = (start + end) / 2;
			int count = 1;

			for (int i = 0; i < n; i++) {
				sum += arr[i];
				if (sum > mid) {
					sum = arr[i];
					count += 1;
				}
			}
			if (count <= m) {
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		}
		return start;
	}
}