백준 2343번: 기타레슨

문제 링크 : https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

 

 

 문제 설명 

 

레슨의 수 와 블루레이의 수가 주어지고 그다음줄에 레슨의 길이가주어짐

레슨을 블루레이에 나눠서 녹음할껀데

1. 순서가 바뀌면 안되고

2. 블루레이의 길이를 최소로 해야됨 

3. 최소 블루레이 길이 출력

 

 알고리즘 

 

이분 탐색 알고리즘으로 최소 블루레이 길이를 구하면 된다.

 

low는  레슨길이중 최대값으로 지정 ( 레슨길이보다 low 가 작을 경우 레슨이 아예 녹음 되지 않음 )

hi는 INF로 지정 밑에는 간단히 예시

 

1. low = 9 , hi = 20 -> mid =14

(1,2,3,4)(5,6)(7)(8)(9) - > 블루레이 개수 = 5 -> low를 mid+1 로

 

2. low = 15 ,hi = 20 ->mid = 17

(1,2,3,4,5)(6,7)(8,9) -> 블루레이 개수 :3 -> high를 mid-1로

 

3. low = 15,hi = 16 -> mid =15

(1,2,3,4,5)(6,7)(8)(9) -> 블루레이 개수 :4 -> low 를 mid+1 로

 

4. low = 16, hi =16 -> mid = 16

(1,2,3,4,5)(6,7)(8)(9) -> 블루레이 개수 : 4-> low를 mid+1로

 

5. low=17 , hi=16 -> low > hi 이므로 while 문 종료후 low 출력 .

 

 코드 

#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
 
using namespace std;
typedef long long ll;
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int N, M;
    cin >> N >> M;
 
    vector<ll> blue(N);
    ll hi = 1000000;
    ll lo = 0;
    for (int i = 0; i < N; i++) {
        cin >> blue[i];
        lo = max(lo, blue[i]);
    }
 
    while (lo <= hi) {
 
        //필요 블루레이의 갯수 
        int cnt = 1;
 
        ll mid = (lo + hi) / 2;
        ll sum = blue[0];
 
        //최소 필요 블루레이의 갯수를 구하는 과정
        for (int i = 1; i < N; i++) {
            if (sum + blue[i] > mid) {
                cnt++;
                sum = 0;
            }
            sum += blue[i];
        }
 
        if (cnt <= M)hi = mid - 1;
        else lo = mid + 1;
    }
 
    cout << lo;
}

참고 블로그 :https://alswnsdl.tistory.com/7 

while문에서  계속 값이 1 씩 어긋나서 결국 다른사람의코드를 참고 하였다.