43. 뮤직비디오 (이분검색 응용 : 결정 알고리즘)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main()
{
    // freopen("input.txt", "rt", stdin);

    int n, m, lt, rt, i, tmp, sum = 0, max, cnt = 1, mid = 0;

    scanf("%d %d", &n, &m);

    vector<int> a;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &tmp);
        sum += tmp;
        a.push_back(tmp);
    }

    lt = 1;
    rt = sum;

    while (lt <= rt)
    {
        mid = (lt + rt) / 2;

        sum = 0;
        cnt = 1;
        for (i = 0; i < n; i++)
        {
            if (sum + a[i] > mid)
            {
                cnt++;
                sum = a[i];
            }
            else
            {
                sum += a[i];
            }
            //	printf("cnt: %d, sum: %d, mid: %d\n", cnt, sum, mid);
        }

        if (cnt > m)
            lt = mid + 1;
        else
        {
            max = mid;
            rt = mid - 1;
        }
    }

    printf("%d", max);

    return 0;
}

 

 

1. 가능한가를 결정할 수 있다면, 이분 검색을 통해 가능한 범위를 줄여나갈 수 있다. 
2. lt와 rt의 범위를 조심할 것.
3. mid = (lt+rt)/2에서 (lt+rt)가 홀수인 경우 계산은 내림으로 된다. (int형이므로 소수 값을 버리므로)