백준 2343 기타레슨 c++ [컴공과고씨]

https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

 

문제 정리

강의를 녹화해야함.

강의 수 N개, M개의 블루레이에 저장.

이때 강의마다 시간이 주어지는데 강의는 순서대로 녹화해야함.

또한 강의 중간에 끊겨서 녹화하면 안됨. -> 한 강의는 한 블루레이에 끊어지지 않고 있어야함.

이때 블루레이의 크기를 구하는데 최소 크기를 구해야함.

 

문제 해결 방법

하나하나 크기를 정해서 비교하면 시간이 굉장히 오래 걸리게 됩니다.

그러므로 이분탐색을 이용하여서 시간 단축을 해주어야 합니다.

최소값 1 최대값은 모든 강의시간을 모두 합한 값.

 

이분탐색 시작

초기 블루레이 값을 최소값과 최대값의 평균으로 해줌.

블루레이 개수 초기값은 1로 시작

블루레이 크기가 애초부터 강의시간 보다 작다면 성립 x

남은 블루레이 공간이 다음 강의를 모두 담지 못하면 다음 블루레이 사용.

남은 블루레이 공간을 블루레이 초기 크기로 바꾸어줌. 이때 블루레이 개수 카운트 1 증가.

남은 블루레이 공간에서 강의 시간 차감.

 

블루레이 개수가 M보다 크면 블루레이 초기 크기를 늘려줌.

아니면 블루레이 크기 값을 저장 후 블루레이 크기를 작게하여 다시 탐색.

 

전체 코드 및 주석

#include <iostream>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
 
    int lesson[100002];
    int low, high;
    high = 0; // 최대값
    low = 1; // 최소값
    int a;
    for (int i = 0; i < n; i++){
        cin >> a;
        lesson[i] = a;
        high += a;
    }
    int mid;
    int total; // 녹화중인 블루레이의 남은 공간
    int result = 0;
 
    while (low <= high){
        mid = (low + high) / 2;
        total = mid; // 초기 블루레이 공간
        bool possible = true;
        int cnt = 1; // 블루레이 개수 1로 시작
        for (int i = 0; i < n; i++){
            if(mid < lesson[i]){ // 블루레이 크기가 애초부터 강의보다 작다면 성립 x
                possible = false;
                break;
            }
            if(total < lesson[i]){ // 남은 공간이 다음 강의를 모두 담지 못하면 다음 블루레이 사용
                total = mid; // 다음 블루레이 사용
                cnt++; // 블루레이 개수 카운트
            }
            total -= lesson[i]; // 공간 차감
        }
        if (cnt > m || !possible){ // 성립하지 않거나 정해진 블루레이 개수 보다 더 많이 사용 했을 경우
            low = mid + 1; // 블루레이 크기를 늘려줌
        }else if (cnt <= m){ 
            high = mid - 1; // 블루레이 크기 작게
            result = mid; // 크기 값 저장
        }
    }
    cout << result << endl; // 결과 출력
 
    return 0;
}

체감 난이도	걸린시간	후기	사용 알고리즘
중하	35m	x	이분탐색