문제

기타 레슨

풀이

이번에도 이분탐색 문제인데 이분탐색 문제가 내기준 가장 애매하게 느껴지기 때문에 연습하고 있다. 어떻게 보면 브루트 포스로도 풀 수 있을 것만 같은데 최대 10만개의 강의가 있고 최대 10만번 블루레이의 개수를 비교해야 하기 때문에 이분탐색으로 푸는 문제이다

가장 중요한 여기서 이분탐색 해야 하는 것은 블루레이의 크기이다
그렇다면 최소 블루레이의 크기는 어떻게 되는걸까?
이것부터가 나는 틀렸었는데 블루레이에 음악이 강의가 들어가기 위해서는 강의의 길이가 블루레이의 길이보다 작아야 한다 는 전제 조건이 있다
그렇다면 강의의 길이가 가장 긴 것보다 블루레이의 크기가 커야 하기 때문에 강의의 길이 중 가장 큰 것이 가장 작은 블루레이의 크기 가 된다.

그리고 가장 큰 블루레이의 크기는 강의가 전부 들어갈수 있는 블루레이 한개의 크기가 된다

int min = 0;
int max = 0;
for (int i = 0;i < n; i++) {
	time[i] = Integer.parseInt(st.nextToken());
    max += time[i];
	min = Math.max(time[i]);
}

모든 블루레이가 모두 같은 길이라고 했지만 한개의 블루레이에 담겨진 영상의 총 길이는 정해진 길이보다 작거나 같기만 하면 된다. 이부분에서 제일 헷갈렸다.

while (min <= max) {
	int current = 0; // 현재 블루레이에 담긴 영상의 길이
    int count = 0; // 블루레이의 개수
    int mid = (min + max) / 2;
    
    for (int i =0; i < n; i++) {
    	// 현재 블루레이에 현재 영상을 담기 위해 블루레이의 크기보다 크다면
        // 새로 블루레이를 추가한다
    	if (current + time[i] > mid) {
        	current = 0;
            count++;
        }
        // 현재 강의를 블루레이에 담는다
        current += time[i];
	}
    
    // 강의가 전부 담기지 않았다면 한개의 블루레이를 추가한다
    if (current != 0) {
    	count++;
    }
    
    // m개의 블루레이가 다 만들어지지 않았다면 블루레이의 크기를 줄여준다
    if (count <= m) {
    	max = mid - 1;
    } else {
    	min = mid + 1;
    }
}

전체 코드

전체 코드