2343번-기타레슨

문제

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

2343번: 기타 레슨

---

접근방법

이분탐색에서는 비교대상 (저의 코드에서는 mid 변수가 이것을 의미합니다.)을 어떻게 설정해줘야 하는것이 가장 중요합니다. 저는 "블루레이의 크기"를 mid 값으로 설정하였습니다. 예시를 들자면 블루레이의 크기를 10으로 설정하고 각 레슨들(arr의 값들)의 크기를 더해주면서 10을 넘을 경우 cnt값을 올려 총 블루레이의 갯수에 따라 left값과 right을 변경하였습니다. 이 문제의 주의해야할점은 m의 범위가 1 < m 이기 때문에 최소 cnt를 1로 설정해주어야 합니다.

---

정답코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX =  1e5 + 1;
 
int n , m;
ll arr[MAX];
int main(void)
{
    fastio;
    cin >> n >> m;
    ll lowValue = 0;
    ll maxValue = 0;
    for(int i = 0; i < n; i ++)
    {
        cin >> arr[i];
        maxValue += arr[i];
        lowValue = max(lowValue, arr[i]);
    }
 
    ll left = lowValue;
    ll right = maxValue;
    ll ans;
    while(left <= right)
    {
        ll mid = (left + right) / 2;
        ll cnt = 1, sum = 0;
        for(int i = 0; i < n; i++)
        {
            if(sum + arr[i] > mid)
            {
                cnt++;
                sum = 0;
            }
            sum += arr[i];
        }
        
        if(cnt <= m)
        {
            right = mid - 1;
            ans = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    cout << left << "\n";
}