[Algorithm]Baekjoon 17951번 :: 흩날리는 시험지 속에서 내 평점이 느껴진거야

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
#include <mutex>
 
using namespace std;
 
int n, k;
int papers[100000];
 
 
bool check(int mid)
{
    int sum = 0;
    int count = k;
    
    for (int i = 0; i < n; ++i)
    {
        sum += papers[i];
 
        if (sum >= mid)
        {
            --count; // 그룹개수 카운팅
            sum = 0;
 
            if (count == 0)
            {
                return true;
            }
        }
    }
 
    return false;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> k;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> papers[i];
    }
 
    int left = 0;
    int right = 0x3f3f3f3f;
    int answer = 0;
 
    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (check(mid))
        {
            left = mid + 1;
            answer = mid;
        }
        else
        {
            right = mid - 1;
        }
    }
 
    cout << answer;
}

 

 

주어진 문자 그대로 완탐을 한다고 가정하면, 그룹을 가지각색으로 나눠야 하기 때문에 시간복잡도가 매우매우 복잡해진다.

그러니 구해야하는 최소값을 고정시킨 후, 시험지를 앞에서부터 검사하면서 최소값을 만족시키는 누적값이 완성될 때마다 카운팅을 한다.

이 카운팅값이 k값보다 크다면, 즉 조건을 만족할 경우 이 고정된 최소값은 문제에서 요구하는 값들 중 하나가 된다.

이렇게 이 고정값들을 이분탐색시키면서 조절하면 정해를 구할 수 있다.