인프런 커뮤니티 질문&답변

jarchive님의 프로필 이미지

작성한 질문수

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

43. 뮤직비디오 (이분검색 응용 : 결정 알고리즘)

혼자 해봤을 때 안되서 질문합니다.

작성

·

213

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;

}

답변 2

1

jarchive님의 프로필 이미지
jarchive
질문자

네 알겠습니다! 답변 감사합니다 선생님!

1

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^ 

데이터를 드렸으니 틀리는 데이터를 가지고 버그를 스스로 잡아야 합니다. 그렇게 해야지 실력이 늡니다. 

위 코드의 경우 사소한 실수입니다. Count 함수의 for문이 모든곡을 순회하는지 생각해보세요.

jarchive님의 프로필 이미지

작성한 질문수

질문하기