작성
·
221
0
안녕하세요 선생님.
선생님 설명을 듣고 이해가 됬다고 생각했습니다.
다 지우고 혼자 짜봤는데 테스트케이스가 100점이 안나오네요.
어디가 문제인지 모르겠습니다. 도와주시면 감사하겠습니다.
#include <stdio.h>
int song[1001], cnt_limit_dvd;
int Count(int size){
int i = 0, cnt_dvd = 1, sum = 0;
for(i=1; i<=size; i++){ // 모든 곡 순회
if(sum + song[i] > size){
cnt_dvd++;
sum = song[i];
}else{
sum += song[i];
}
}
return cnt_dvd;
}
int main(int argc, char** argv){
int i = 0, cnt_song = 0;
int lp = 1, rp = 0, mid = 0, res = 0;
int max_value = -2147000000;
//freopen("input.txt", "rt", stdin);
scanf("%d %d", &cnt_song, &cnt_limit_dvd);
// 곡들이 총 몇분인지 저장
for(i=1; i<= cnt_song; i++){ // 인덱스 1 부터 사용
scanf("%d", &song[i]);
rp = rp + song[i];
if(song[i] > max_value) max_value = song[i]; // 제일 긴 곡 저장
}
// dvd 한 개의 용량이 '제일 긴 곡'의 용량보다는 같거나 커야 한다.
// 가능한 dvd 의 시간 범위 : 1분 부터 rt에 저장된 분
//이분검색
while(lp <= rp){
mid = (lp + rp) / 2; // dvd 1개의 최소 용량
if(mid >= max_value && Count(mid) <= cnt_limit_dvd){ // mid 가 답이 된다.
res = mid;
rp = mid - 1;
} else {
lp = mid + 1;
}
}
printf("%d", res);
return 0;
}