[c++] 2343번: 기타 레슨

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

2343번: 기타 레슨

 

문제 요약

- 블루레이에는 총 N개의 강의가 들어간다. (강의 순서가 바뀌면 안됨)
   → i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

- M개의 블루레이에 모든 강의 동영상 녹화
   → 블루레이의 크기(녹화 가능한 길이) 최소
   → 블루레이는 모두 동일한 크기

= 가능한 블루레이의 크기 중 최소를 구하라.

범위

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

힌트

N = 9, M = 3
1번 블루레이에 1, 2, 3, 4, 5 | 2번 블루레이에 6, 7 | 3번 블루레이에 8, 9 넣으면 각 블루레이의 크기는 15, 13, 17이 된다.
블루레이의 크기는 모두 같아야 하므로, 블루레이의 크기는 17 → 17보다 작은 크기의 블루레이를 만들 수 없다.

 

✏️ 매개변수 탐색으로 해보기

 

---

 

이 문제를 거꾸로 생각해서 풀어보자.

→ 블루레이 크기(S)가 __ 일 때, M개의 블루레이가 만들어지는가?

 

탐색 범위 생각해보기

 

블루레이의 크기 탐색 범위가 최대 강의 길이보다 커야한다. 그러므로 탐색 범위의 L은 입력받은 강의의 최대 길이로 설정한다.

만약 블루레이가 한 개(M=1)고, 강의가 100,000개(N=100,000)인 경우에서 모든 강의의 길이가 10,000(분)라면?

10,000 x 100,000 = 1,000,000,000 이므로 탐색 범위의 R은 1,000,000,000 으로 설정한다. 

 

solution

 

이분 탐색으로 블루레이 크기를 탐색했다. 해당 값의 블루레이 크기로 M개의 블루레이가 만들어지는지 계산하는 calc( ) 함수를 사용한다.

 

  1. 최대 블루레이 크기(size) < 지금까지의 크기(sum+x[i])

     - cnt ++ : 블루레이 하나 추가

     - sum = x[i] : size보다 크면 안된다. 원소 x[i] 때문에 size를 넘겼기 때문에 이 원소부터 다시 sum을 시작하는 것이다!

  2. 최대 블루레이 크기(size) >= 지금까지의 크기(sum+x[i])

     - sum += x[i]

 

//2343번: 기타 레슨
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, x[100002], _max = -1;

void input(){
    cin >> n >> m;
    for(int i=0; i<n; i++) {
        cin >> x[i];
        _max = _max < x[i] ? x[i] : _max;
    }
}

bool calc(int size){
    int cnt = 1, sum = 0;
    for(int i=0; i<n; i++){
        if(sum + x[i] > size){
            cnt++;
            sum = x[i];
        }else{
            sum += x[i];
        }
    }
    return cnt <= m;
}

void solution(){
    int L = _max, R = 1000000000, ans = 0;
    while(L<=R){
        int mid = (L+R)/2;
        if(calc(mid)){
            ans = mid;
            R = mid - 1; //최소를 찾아야 되기 때문!!
        }else{
            L = mid + 1;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    input();
    solution();
    return 0;
}

 

 

처음에 문제를 읽었을 땐, 각 블루레이에 모두 동일한 강의를 넣어야 되는 줄 알았다. 근데 예제입/출력값과 힌트를 보니 각 블루레이에는 다른 강의가 들어간다는 것을 보고 문제를 제대로 읽자고 다시 다짐했다. (128347950번째 다짐)

 

첫 제출은 틀렸는데, 입력값이 정렬된 상태로 들어오는 것으로 착각했다.. 예제 입력값만을 믿고 하면 안되는데,, 문제 해석을 제대로 하지 않은 것이 요인이다. 입력의 최대값만 알면 되므로 후딱 입력함수에서 최댓값을 입력받으면서 업뎃해주는 것으로 수정해줬다.

 

최대값을 구하는 문제만 풀다가 최솟값을 구하는 문제는 처음 푸는데 역시 헷갈리는 점이 많은 문제였다.

역시 설명하는 건 어려워...😱

 

---

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다. 만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
     언제나 환영합니다. 감사합니다. 화이팅!☃️