BOJ 2343 기타 레슨

 

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

문제 분석

처음에는 어떻게 풀어야 할 지 감이 아예 안잡혔다. 블루레이 길이를 찾아야하는데 강의의 수의 범위가 꽤 커서 이분 탐색을 써야한다는 느낌은 들었지만 어떻게 적용할지 몰랐다. 개강 전부터 풀고 있다가 개강하고 나서 풀게 되었다..

이분 탐색을 무슨 값으로 할 지 모르겠어서 어려웠던 것 같다. 이를 블루레이의 길이(l)로 잡았을 때 가능했다.

---

풀어 보기

이분 탐색을 진행할 때 start(최솟값)를 블루레이의 최댓값으로 해야 모든 블루레이를 담을 수 있다.(l이 1~9일 때 담는 크기가 1~8이면 9인 블루레이를 담을 수 없다) end(최댓값)는 모든 블루레이의 합이 되면 된다. 반복문을 돌 때 필요한 블루레이수 cnt와 m을 비교하여 cnt가 더 크다면 start가 더 커야한다.

---

코드 구현

#include <bits/stdc++.h> // 2343 기타 레슨
using namespace std;
int n, m;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int Max = 0;
    int sum1 = 0;
    int cnt = 0;
    cin >> n >> m;
    vector <int> blueray(n);
    for(int i = 0; i < n; i++){
        cin >> blueray[i];
        Max = max(blueray[i], Max);
        sum1 += blueray[i];
    }
    int start = Max;
    int end = sum1;
    int mid;
    while(start <= end){
        int cnt = 0;
        int sum2 = 0;
        mid = (start + end) / 2;
        for(int i = 0; i < n; i++){
            if(sum2 + blueray[i] > mid){
                sum2 = 0;
                cnt++;
            }
            sum2 += blueray[i];
        }
        if(sum2 != 0) cnt++;
        if(cnt > m) start = mid + 1;
        else end = mid - 1;
    }
    cout << start;
}

if(sum2 != 0) cnt++; 이 부분을 구현 안해서 자꾸 틀렸다. 항상 모든 테스트케이스를 맞아야 한다는 것을 생각하면서 구현해야겠다. 추가로 다른 자료를 보니 내가 변수를 쓸데없이 많이 작성함을 발견했다. 더 깔끔하게 구현해보도록 노력하겠다.

#include <bits/stdc++.h> // 2343 기타 레슨
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <int> a(n);
    int start = 0;
    int end = 0;
    
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(start < a[i])
        	start = a[i]; // 레슨 최댓값 -> 시작 인덱스
        end += a[i] // 모든 레슨의 합 -> 종료 인덱스
    }
    
    while(start <= end){
        int mid = (start + end) / 2;
        int sum = 0;
        int cnt = 0;
        
        for(int i = 0; i < n; i++){
            if(sum + a[i] > mid){
                sum = 0;
                cnt++;
            }
            sum += a[i];
        }
        if(sum != 0) cnt++;
        if(cnt > m) start = mid + 1;
        else end = mid - 1;
    }
    cout << start;
}

굳이 Max와 sum1, 2를 나눠서 저장할 필요가 없었다. blueray도 그냥 a같은 쉬운 문자를 쓰는 것이 좋을 것 같다.