[백준] 2343 - 기타 레슨 (C++)

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

블루레이에는 총 N개의 강의가 들어가고, 강의의 순서는 바뀌면 안된다. (i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.) 크기가 같은 M개의 블루레이에 모든 기타 강의 동영상을 녹화하려고 할 때, 블루레이 크기의 최솟값을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ N

 

각 강의의 길이는 10,000분을 넘지 않는다. 따라서 int 범위 안에서 해결 가능하다. (10,000 × 100,000)

 

이분탐색으로 mid 값을 구하고 반복문을 통해 강의 길이의 합이 mid 값을 넘지 않도록 블루레이를 만들고, 블루레이의 개수가 M을 넘지 않으면 답으로 출력할 값을 갱신하는 것을 반복한다.

 

가능한 블루레이 크기 중 최솟값을 구해야 하므로 종료 조건을 잘 설정해야 한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M, 강의의 길이 입력 받기
2. 블루레이의 크기를 정하고 강의들을 연속으로 넣었을 때 M개 이하의 강의가 나오는 경우, 블루레이의 크기가 최솟값이라면 갱신하며 이분탐색을 진행
3. 블루레이 크기의 최솟값을 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

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

int n,m,x,x_sum,ans=1e9+1,mx;
vector<int> v;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i=0; i<n; i++) {
        cin >> x;
        v.push_back(x);
        x_sum += x;
        mx = max(mx,x);
    }

    int l=mx-1,r=x_sum+1;
    while (l+1<r) {
        int mid=(l+r)/2, sum=0, cnt=0;

        for (int i=0; i<n; i++) {
            sum+=v[i];
            if (sum>mid) {
                cnt++;
                sum=v[i];
            }
        }
        if (sum<=mid) cnt++;
        
        if (cnt>m) {
            l=mid;
        }
        else {
            r=mid;
            ans = min(ans,mid);
        }

    }

    cout << ans;
}