06.03. 기타 레슨 [Binary Search & Parametric Search][백준 2343]

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

2343번: 기타 레슨

 

Algorithm classification : Binary Search, Parametric Search

 

06.03.1. Problem

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

 

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

 

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

 

 

06.03.2. Input limit

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

 

 

06.03.3. Output

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

 

 

06.03.4. Solution

블루레이의 길이 최솟값을 이분탐색으로 찾는 것입니다. 이분탐색에서 MID는 항상 구하고자 하는 값이 되어야 합니다. 매개변수 탐색에서 한가지 tip은 탐색과정을 trace하는 것입니다. UPDATE의 조건으로 사용되는 값과 LEFT, RIGHT, MID를 출력해가면 되겠군요. 몇 개의 corner case가 주어진다면 어느 분할 과정에서 어긋나는지 확인하면 쉽게 code를 수정하실 수 있을 겁니다.

	int n, m, i;
	scanf("%d %d", &n, &m);
	int a[n], left = 0, right = 10000, mid;
	int ans = 0;
	
	for(i = 0; i < n; i++){
		scanf("%d", &a[i]);
		left = max(left, a[i]); 
	}
	
	long long sum = 0;
	long long temp;
	 
	while(left <= right){
		mid = (left + right) / 2;
		temp = 0;
		sum = 0;
	
		for(i = 0; i < n; i++){
			if(sum + a[i] <= mid){
				sum += a[i];
			}
			else{
				sum = a[i];
				temp++;
			}
			//printf("%d %d\n", sum, temp);
		}
		
		//printf("%d %d : %d > %d %d\n", left, right, mid, sum, temp);
		
		if(temp <= m){
			right = mid - 1;
		}
		else{
			left = mid + 1;
		}
	}

 

참고로 Greedy Algorithm을 생각하셔서 정렬을 시도하실 수도 있는데 i번 레슨과 j번 레슨을 같은 블루레이에 녹화하면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화한다는 조건이 있기 때문에 정렬을 하시면 안됩니다. 물론 이런 조건이 없으면 더 빠른 시간이 나오게 코드를 수정해주어야겠죠.

 

 

몇 개의 test case를 아래에 두겠습니다. 왜 그런지 모르겠지만 이번 문제는 제가 note해둔 test case가 많네요. 아마 여러번 제출했는데 실패했던 모양입니다.

4 2
1 1 1 1
>> 2

5 2
2 5 5 3 3
>> 11

5 4
5 5 2 5 1
>> 6

4 2
5 1 2 5
>> 7

12 3
10 8 7 2 8 9 4 12 7 5 2 9
>> 33

12 5
7 3 3 10 4 8 7 9 2 2 12 2
>> 15

7 7
5 9 6 8 7 7 5
>> 9
 
8 7
3 3 10 10 3 2 6 2
>> 10

7 7
1 5 9 9 9 2 9
>> 9

5 2
1 1 1 1 100
>> 100

50 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
>> 105

50 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
>> 1275

50 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
>> 435

50 50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
>> 50