https://www.acmicpc.net/problem/2343
강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.
강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.
강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.
출력
첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.
풀이 아이디어
매개변수 탐색을 활용해서 좌우 범위를 각각 start, end로 가정했다.
start = 가장 긴 강의 하나
end = 모든 강의 길이의 합
mid = (start+end)//2
start를 '가장 긴 강의 하나'로 잡은 이유는 블루레이 크기가 작아
강의가 잘리는 일을 막기 위해서다.
end는 나누는 블루레이 갯수가 m이라고 할 때, m은 최소 1이므로
이 경우 모든 강의를 담을 수 있어야 하기 때문이다.
mid는 예상 블루레이 크기를 의미한다.
예상 블루레이 크기값 mid를 기준으로 담아보며 필요한 블루레이 바구니 수 count를 계산한다.
count가 목표하는 블루레이 수 m개와 비교해서
- 1) count>m이면 예상 블루레이 크기 mid가 최적 목표보다 작았다는 것을 의미하므로
블루레이 크기를 더 높은 값에서 탐색할 수 있도록 start=mid+1로 하여 다시 탐색한다. - 2) count<=m이면 예상 블루레이 크기 mid가 최적 목표보다 크거나 같다는 것을 의미하므로
블루레이 크기를 더 낮은 값에서 탐색할 수 있도록 end=mid-1로 하여 다시 탐색한다.
조건을 만족하는 값을 찾는 것과 동시에
혹시 더 낮은 값도 조건을 만족하는지 확인하기 위해서다.
매개 변수 탐색
매개변수 탐색(Parametric Search)이란?
'최적화 문제'를 '결정 문제'로 치환해서 푸는 탐색 기법이다.
그리고 '결정 문제'로 판단하는 과정에서 이분 탐색이 활용된다.
'최적화 문제' = 어떤 조건을 만족하는 최적의 해를 구하기
'결정 문제' = YES or NO로 대답할 수 있는 문제
예를 들어, 여러 물건이 있고 바구니 3개에 담고자할 때
각 바구니가 담을 수 있는 최대 무게를 구하고자 한다면
예상한 최대 무게를 기준으로 담아보며 실제로 몇개의 바구니가 담기는 지를 확인하고
실제로 담긴 바구니 갯수에 따라서 예상한 최대 무게를 수치 조정을 하면 된다.
언제 쓸 수 있을까?
- 결정 문제를 풀고자 할 때
- 어떤 조건을 만족하는 최대값, 최솟값을 구할 때
vs 이분 탐색
이분 탐색은 순서대로 정렬된 배열에서 기준값보다 큰지 작은지로 해당하는 값을 찾는다면
매개 변수 탐색은 순서대로 정렬된 배열이 있을 때 특정 조건을 만족하는 최적의 해를 찾는다면 보면 된다.
이때 최적의 해는 꼭 배열에 있는 값이 아니다.
트러블 슈팅
구현과정에서 실수한 부분이 있는데 다음에 같은 실수를 하지 않도록 공유하고자한다.
1) 강의를 담는 조건문 설정 실수
예상 블루레이 크기 mid를 기준으로 강의를 하나씩 담을 때
처음에는 아래처럼 구현했다.
이 코드의 문제는 "못 담을 때" 다음 블루레이를 추가해야하는데
"="를 잘못줬다.
아래는 조건문을 수정한 코드이다.
2) 탐색하는 mid값 조정 실수
예상 블루레이 크기 mid를 기준으로 담아 count를 계산하고 난 후
탐색 범위를 조정하는 과정에서 실수를 했다.
처음에는 아래처럼 했는데 "조건을 만족하는 최대값"을 구하게 되었다.
하지만 우리가 구하고자 하는 것은 "조건을 만족하는 최소값"이므로 코드를 아래처럼 수정했다.
여기서 "count<=m"은 조건을 만족하더라도 더 작은 값이 되는지 확인하겠다는 의미다.
풀이 코드
import java.io.*;
import java.util.*;
public class _2343_ch {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// n,m 입력
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
// 강의 입력
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
// arr 최대값 maxLecture와 모든 강의 합 lectureSum 구하기
int longestLecture=arr[0];
int lectureSum=arr[0];
for(int i=1;i<arr.length;i++){
lectureSum+=arr[i];
if(arr[i]> longestLecture){
longestLecture=arr[i];
}
}
int start = longestLecture;
int end = lectureSum;
// 매개 변수 탐색
while(start<=end){
int mid = (start+end)/2;
int sum = 0;
int count = 1;
// 블루레이 크기가 mid일 때 몇개가 담기는지 확인한다.
for(int i=0;i<arr.length;i++){
// 담을 수 있으면 담자
if(sum+arr[i] <= mid){
sum+=arr[i];
}
// 담을 수 없으면 다음 블루레이에 담자
else if(sum+arr[i] > mid){
count++;
sum=arr[i];
}
}
// mid일 때 담기는 갯수 count를 m과 비교한다.
if (count > m){
start=mid+1;
}
// mid가 조건을 만족하더라도 더 작은 값도 되는지 확인한다.
else if (count <= m){
end=mid-1;
}
}
System.out.println(start);
}
}