백준 2343 (기타 레슨) c++

문제

2343번: 기타 레슨

n개의 강의를 m개의 블루레이에 담으려 하는데 블루레이의 최소크기를 출력하면 되는 문제입니다.

예를들어 n이 9이고 m이 3이면 

9개의 강의 {1, 2, 3, 4, 5, 6, 7, 8, 9} 를 담으려 한다면 블루레이의 크기는 17이 최소입니다.

비디오는 순서대로 연속적으로 블루레이에 담아야합니다.

 

블루레이의 크기가 클 수록 모든 비디오를 담을 수 있습니다. 

블루레이의 특정크기(k)에 대해서 레슨이 모두 저장되는가?

저장된다면, k보다 큰 크기에 대해서도 항상가능합니다.

 

따라서 parametric search를 이용해서 문제를 해결하였습니다.

int s = *max_element(arr, arr+n);
int e = 1000000000;
while (s < e) {
    int m = (s + e) / 2;
    if (search(m)) {
        answer = min(answer, m);
        e = m;
    }
    else s = m + 1;
}
cout << answer;
 
 
bool search(int key) {
    int ans = 0;
    int cnt = 1;
    for (int i = 0; i < n; i++) {
        if (ans + arr[i] > key) {
            cnt++;
            ans = 0;
        }
        ans += arr[i];
    }
    if (cnt <= m)return true;
    return false;
}

먼저 start는 주어진 강의중 제일 큰 크기가 들어갔습니다. 

아무리 블루레이가 작아도 가장 큰 강의보다 크기 때문입니다.

 

14번쨰 줄을 보면 이제 강의를 차례대로 확인하면서 블루레이에 넣을 수 있는지 없는지 확인합니다.

ans변수는 강의의 누적합을 저장하면서 key(블루레이의 크기) 보다 작으면 계속 해서 누적합을 저장하고

key보다 작으면 더이상 블루레이에 강의를 넣을 수 없다는 의미이므로 cnt를 1늘려주고 ans는 다시 0이 되어

다음 강의를 누적합으로 저장합니다.

 

24번째 줄을 보면 cnt(블루레이의 갯수)가 m보다 작거나 같다는 의미는 현재 블루레이의 크기가 여유 있다는

의미 이므로 true를 return합니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n, m, answer=1000000000;
int arr[100001];
bool search(int key);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    //sort(arr, arr + n);
 
    int s = *max_element(arr, arr+n);
    int e = 1000000000;
    while (s < e) {
        int m = (s + e) / 2;
        if (search(m)) {
            answer = min(answer, m);
            e = m;
        }
        else s = m + 1;
    }
    cout << answer;
 
    return 0;
}
bool search(int key) {
    int ans = 0;
    int cnt = 1;
    for (int i = 0; i < n; i++) {
        if (ans + arr[i] > key) {
            cnt++;
            ans = 0;
        }
        ans += arr[i];
    }
    if (cnt <= m)return true;
    return false;
}