[백준 2343] 알고리즘 65일차 : 기타 레슨

www.acmicpc.net/problem/2343

2343번: 기타 레슨

 

이분탐색 C++

음 메모리 파티션을 나눈다고 생각하면 이해가 쉬울 것 같다. N개의 레슨 영상의 시간이 주어지고

이걸 용량이 동일한 M개의 usb에 담아야할때 usb용량의 최소크기를 구하는 것이다. (내맘대로 문제 변경)

 

접근방법

우선 이분탐색이기 때문에 범위만 산정되고 기준을 정하는 함수만 설계하면 끝난다.

범위는 레슨 길이 중 최댓값 ~ 모든 레슨 길이의 합이다.

*처음 제출할때 이분 탐색 start 값을 1로 설정해서 레슨 1개가 용량을 초과해도 통과 되는 코드라 틀렸었다.(58%에서 틀렸습니다 뜸)

그리고 isOver함수는 한 usb에 들어가는 영상 길이의 합을 저장하는 total변수와 필요한 usb개수인 cnt 변수를 사용한다.

cnt는 초기값을 1로 설정하든지 마지막에 1을 더해야한다. (마지막 usb에 들어가는 레슨 수가 하나일 경우 집계되지 않기 때문)

레슨의 수 만큼 반복문을 돌면서 total에 현재 레슨 길이를 더한 값이 cap (usb용량)을 넘지 않으면

total에 현재 레슨 길이를 더하고 계속 반복문을 돈다.

넘으면 더하지 않고 total 값을 현재 레슨 길이로 변경한 뒤 (total값을 초기화)

cnt를 1 증가 시킨다. (usb용량이 차서 또 다른 usb를 사용) 오늘 비유 좋네요.

그리고 마지막으로 for문을 다 돌면 cnt 값(필요한 usb개수)가 M(갖고있는 usb개수)보다 크면 true를 반환

작거나 같으면 false를 반환

 

소스코드

#include <iostream>
using namespace std;
int N, M;
int arr[100000];
int sum;
bool isOver(int cap){
    int cnt = 1;
    int total = 0;
    for(int i = 0 ; i < N ; i++){
        if(total + arr[i] <= cap){
            total+= arr[i];
        }else{
            total = arr[i];
            cnt++;
        }
    }
    return cnt > M ? true : false;
}
int binarySearch(int s, int e){
    int mid;
    while(s <= e){
        mid = (s+e)/2;
        if(isOver(mid)){
            s = mid+1;
        }else{
            e = mid-1;
        }
    }
    return s;
}
int main(){
    cin >> N >> M;
    int max = 0;
    for(int i = 0 ; i < N ; i++){
        cin >> arr[i];
        if(max < arr[i]){
            max = arr[i];
        }
        sum += arr[i];
    }
    cout << binarySearch(max, sum);
    
    return 0;
}