[ 백준 2343 ] 기타 레슨 (C++) - 이분 탐색

---

🔗 문제 링크

2343번: 기타 레슨

---

💡 문제 풀이 및 해석

1. 블루레이의 사이즈는 최대 10억이다. 따라서 최대 크기를 10억으로 잡아두고 시작한다.
2. 블루레이의 사이즈를 이분탐색으로 정한다.
3. 블루레이에 담기는 순서는 강의의 순서와 같으므로, 순서대로 블루레이에 강의를 담는다.
4. 그렇게 블루레이가 꽉 차면 다음 블루레이에 담기는 순서로 이분탐색을 진행하면 된다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<vector>
using namespace std;

int N, M;
vector<int> lecture;
int answer = 1000000000; // N * 강의
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        int minute; cin >> minute;
        lecture.push_back(minute);
    }
}

bool canMake(int blueRay) {
    int acc = 0;
    int cnt = M;
    for (int lectureTime : lecture) {
        if (lectureTime > blueRay) return false;
        if (lectureTime + acc <= blueRay) {
            acc += lectureTime;
        }
        else {
            cnt--;
            acc = lectureTime;
        }
        if (cnt == 0) return false;
    }
    return true;
}

void sol() {
    int minTime = 0;
    int maxTime = 1000000000;
    int midTime;
    while (minTime < maxTime) {
        midTime = (minTime + maxTime) / 2;
        if (canMake(midTime)) {
            maxTime = midTime;
        }
        else {
            minTime = midTime + 1;
        }
    }
    cout << maxTime;
}

int main() {

    input();
    sol();
    return 0;
}

---

🤔 문제 후기

처음에는 그리디 방식으로 하나씩 넘겨볼까 생각했다. 그런 방식으로는 안된다는 것을 알았고, 블루레이의 사이즈를 정해놓고, 하면 이분탐색으로 풀 수 있겠다 싶었다. 순서가 정해져 있으므로, 차례대로 꽉 찰때까지 넣어주면서 하면 되서 생각보다 구현하는 것은 편했던 문제였다.