백준 기타 레슨(2343)

기타 레슨

1. 힌트

1) 정답이 되는 블루레이의 크기는 아무리 적어도 가장 작은 레슨의 길이보다 같거나 클 것이고, 아무리 커도 모든 레슨의 길이를 합친 것 보다는 같거나 작을 것이다. $1 \le x \le 10000 \times N$

2) $x$의 크기의 블루레이 $m$개로 주어진 레슨을 모두 담는다고 할 때, 한 블루레이에 담을 수 있는 한 최대한 담는 것이 최적해이다.

3) $x$의 크기의 블루레이 $m$개로 모두 담을 수 있다면 당연히 $x + 1$

2. 접근

1) 순서를 강제할 수 있을까?

블루레이의 크기는 모드 같아야 하므로 블루레이의 크기가 $x$라고 할 때, $m$개의 블루레이로 레슨을 최대한 담으려면 어떻게 담아야 할까?
최적해를 어떻게 구하는지는 아직 모르지만, 확실한 것은 최적해는 주어진 수열을 $m$개로 나눈 형태일 것이다
$S = \{\{1, 2, 3, 4,5\},\ \{6, 7\},\ \{8,9\}\}$

2) 문제를 분해할 수 있을까?

순서를 강제하면 최적해를 찾는 과정은 주어진 수열의 앞부분에서 어느 정도를 블루레이에 담고 나머지 수열에 대해서 재귀적으로 해결하는 형태가 된다. 블루레이에는 얼마나 담아야 할까? 직관적으로는 최대한 담아야 할 것 같다. 덜 담으면 덜 담은 만큼 재귀호출에 넘기는 수열이 길어지기 때문이다. 귀류법으로 증명해 보자.

어떤 최적해가 최대한 담지 않은 방법으로 만들어졌다고 가정해보자.
$S = \{...,\{...,x_i\},\ \{x_{i+1},...\},...\}$

이제 블루레이의 크기 $x$가 주어지면 $m$개에 나눠서 담을 수 있는지 여부는 $O(N)$의 계산을 통해 알 수 있다. 그렇다면 블루레이의 크기는 $1 \le x \le 10000 \times N$

3. 구현

public class Main {
	static int N; static int[] S;
	
	// i번째 레슨부터 담기 시작할 때,
	// 전체 레슨을 size크기의 m개의 블루레이에 담을 수 있는지 반환
	static boolean f(int size, int m) {
		int capacity = size; m--;
		for (int i = 0; i < N; i++) {
			if (S[i] > size) return false;
			if (capacity >= S[i]) capacity -= S[i];
			else if (m != 0) {capacity = size - S[i]; m--;}
			else return false;
		}
		return true;
	}
	
	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());
		int M = Integer.parseInt(st.nextToken());
		S = new int[N];
		int lo = 0; int hi = 0;
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			S[i] = Integer.parseInt(st.nextToken());
			hi = Math.max(hi, S[i]);
		}
		hi *= N;
		// f(lo) == false && f(hi) == true인 hi를 반환
		while (lo + 1 < hi) {
			int mid = (lo + hi) / 2;
			if (f(mid, M)) hi = mid;
			else lo = mid;
		}
		System.out.println(hi);
	}
	
}

1) 시간 복잡도

$f(x)$의 시간 복잡도는 $O(N)$이고 가능한 블루레이의 크기는 $O(N)$이기 때문에 이분탐색을 사용하면 $O(lgN)$. 그러므로 $O(NlgN)$이 된다.

2) 테스트 케이스