#include <iostream>
int a[1001], n;
int Count(int size){//dvd개수
int i, cnt = 1, sum = 0;
for(i = 1; i <= n; i++){
//모든 곡 탐색
if(sum+a[i] > size){
//a[i]곡은 불가능하다.
cnt++;//새로운 dvd
sum = a[i];
}
else sum = sum + a[i]; //가능하니까 기존 dvd에 곡 녹화
}
return cnt; //필요한 dvd개수 리턴
}
int main() {
int m, i, lt = 1, rt = 0, mid, res, max = -2147000000;
scanf("%d %d",&n,&m);
for(i = 1; i <= n; i++){
scanf("%d",&a[i]);
rt = rt+a[i];//45
if(a[i] > max) max = a[i];
}
while(lt <= rt){
mid = (lt+rt)/2;
if(max <= mid && Count(mid) <= m){
//dvd가 3개 이하로 곡을 녹화할 수 있다면 정답이다.
//그리고, 최소 용량은 곡 중에서 가장 길이가 긴 값보다는 크거나 같아야한다.
//첫번째 반복에서 mid가 23임
//Count(mid)는 2인데
//최소 용량이 23이면 dvd 2개만으로도 가능함.
//그렇다고 틀린게 아님, 최소용량이 23이면 dvd3개로도 가능하기 때문임.
//그래서 Count(mid) <= m으로 조건을 걸어두고 더 좋은 답을 찾기 위해
res = mid;//일단 정답 넣어주고
rt = mid-1; //더 좋은 방안을 찾기 위해 좁히기
}
else lt = mid+1;//답이 아니다.
}
printf("%d\n",res);
return 0;
}
입력은 1~9까지 오름차순된 순열이 존재하고 이를 세개의 DVD로 나누었을 때 DVD용량의 최소를 구해야 한다.
일반적인 문제들은 문제를 읽고 입력을 봤을 때, 코드 시뮬레이션을 해보면서 어떤식으로 풀어야할지 감이 잡힌다.
하지만 이 문제는 코드 시뮬레이션을 돌려봐도 이 정답이(DVD의 용량이)가장 최소화된 것일까? 라는 의문을 품게된다.
즉, 더 나은 정답이 있지 않을까?라는 의문을 품게된다. 그리고 일반적으로 정렬된 값이 주어지거나 정렬을 해야하는 경우에
결정 알고리즘을 사용해야 한다.
풀이 과정
일단 정답(DVD의 최소 용량)은 1~45 중 하나일 것이다.
만약 DVD의 최소 용량이 45(예시)라면? 한 개의 DVD만으로도 입력된 모든 곡들을 저장할 수 있다. 하지만, 입력 값을 보면 세개의 DVD를 사용함으로써 DVD용량을 최소화 시킬 수 있다. 따라서, 이분 검색을 통해 절반으로 줄여보자 그렇다면 이번에는
DVD의 최소 용량이 23(mid)이라면? 두개의 DVD만으로도 입력된 모든 곡들을 저장할 수 있다. 따라서 DVD의 최소 용량은 1~45라는 정답 중에서 23보다 작아도 된다는 것이다.(rt = mid-1)
DVD의 최소 용량이 12(mid)라면? 다섯개의 DVD가 필요하다. 세개를 넘어서버렸다. 따라서, DVD의 최소 용량은 1~ 22이라는 정답 중에서 12보다 커야된다는 것이다.(lt = mid+1)
이제 13~22로 정답의 범위가 줄어들었다. 자 그럼,
DVD의 최소 용량이 17(mid)라면? 세개의 DVD가 필요하다. 즉 우리가 원했던 세개의 DVD로 모든 곡을 담을 수 있다. 그리고 그 최소 용량은 1~45사이의 정답들 중 17이라는 것을 알게되었다.
물론, 최소 용량이 17보다 작은 더 좋은 정답이 있을 수도 있기 때문에 이분 검색은 계속해서 진행하게 된다. (이분 검색은 lt<=rt를 만족한다면 계속 한다)
