[백준 2343] 기타 레슨 C++

문제

백준 2343 기타 레슨 C++

2343번: 기타 레슨

풀이

조건을 보고, 이분 탐색으로 해결할 수 있음을 유추해야 합니다.

순서를 변경하면 안 되고, 모든 동영상을 포함해야 하므로 mid 값에 대해 이분 탐색을 실행합니다.

조건을 만족하면 더 작을 mid 값을, 조건을 만족하지 못한다면 더 큰 mid값을 찾습니다.

 

길이의 합이 int 범위를 넘어설 수 있으므로 long long으로 선언해주고,

mid 값의 최대는 100,000 * 10,000 = 10억이므로 범위에 유의합니다.

 

58%에서 자꾸 틀려서 무엇이 문제인가 고민을 많이 했었는데,

mid값 보다 큰 길이가 있을 경우 녹화가 불가능하므로 조건을 만족하지 않게 됩니다.

따라서 이 때 더 큰 mid값을 찾도록 분기를 구성해줘야 합니다.

소스 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int N, M;
    cin >> N >> M;
 
    vector<int> v;
    int length;
 
    int low = 0;
    int mid = 0;
    int high = 1000000000;
    int result = 0;
    int diskCnt = 0;
    long long lengthSum = 0;
 
    for (int i = 0; i < N; i++)
    {    
        cin >> length;
        v.push_back(length);
    }
 
    while (1)
    {
        if (low > high)
            break;
 
        mid = (low + high) / 2;
        diskCnt = 1;
        lengthSum = 0;
        bool isEnough = true;
 
        for (int diskLength : v)
        {
            lengthSum += diskLength;
 
            if (lengthSum > mid)
            {
                // 디스크 개수 부족
                if (diskCnt >= M || diskLength > mid)
                {
                    isEnough = false;
                    break;
                }
 
                diskCnt += 1;
                lengthSum = diskLength;
            }
        }
 
        if (isEnough)
        {
            high = mid - 1;
            result = mid;
        }
        else
        {
            low = mid + 1;
        }
    }
 
    cout << result;
    return 0;
}