16510. Predictable Queue

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

cin / cout의 입출력 속도를 높이지 않고 풀었을 때 시간초과가 났던 문제이다. 

먼저 일의 개수인 N이 주어진다. 매번 일을 수행할 때 앞에서부터 수행해서 시간안에 할 수 있는 일의 개수를 물어보는 문제이기 때문에 N을 입력받으면서 누적합을 하여 값을 저장해야한다. 단순히 값을 저장할 경우 매번 앞에서부터 합하며 결과를 확인해야하기 때문이다.

다음 과제는 주어진 일의 시간이 어느 구간에 들어가는지를 확인하는 것이다. 일할 수 있는 시간이 충분히 작다면 최대크기의 배열을 생성해서 N을 받으면서 값을 늘려가는 방법으로 들어온 시간을 인덱스로 하여 확인할 수 있지만 시간, 즉 T의 범위가 2*10^9이다. 배열로 만들기에는 너무 큰 수이기 때문에 만들어놓은 N에서 속하는 구간을 찾아야 한다.

M 즉, 시간의 개수가 적다면 누적합 구간을 앞에서부터 탐색해서 처음으로 T보다 큰 값이 나왔을 때의 인덱스를 반환하는 방법을 사용할 수 있다. 하지만 이 문제에서 M의 최대값은 200,000이다. 최악의 경우에 200,000 * 200,000을 수행하게 된다는 뜻. 따라서 다른 방법을 사용해야 한다.

이 때 사용할 수 있는 것이 이분탐색이다. 이분탐색은 수치해석에서 배웠던 이분격자법과 유사하다. 정렬된 배열의 시작과 끝 인덱스를 Left, Right이라고 한다. 이 때, 이 둘의 중간인 (L+R) / 2의 값을 확인한다. 편의상 이 값을 Mid라 한다. 이 때, 찾고자하는 값이 Mid보다 크다면 Left를 Mid로 하고 Mid보다 작다면 Right을 Mid로 한다. 같은 방법으로 값을 찾을 때까지 진행한다. 전체를 탐색할 때에 비해 눈으로 봐도 훨씬 적은 시간이 걸린다는 것을 알 수 있다. 이 과정은 O(N)의 시간복잡도를 O(logN)으로 줄일 수 있다.

출처 : http://wootool.tistory.com/62

- 소스코드 -

#include <iostream>
#include <vector>
 
using namespace std;
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N = 0, M = 0;
    long long input = 0, sum = 0;
 
    vector<long long> v;
    
    cin >> N >> M;
    
    for (int i = 0; i < N; i++)
    {
        cin >> input;
        sum += input;
        v.push_back(sum);
    }
    
    int s = v.size();
    
    
    for (int i = 0; i < M; i++)
    {
        cin >> input;
        int cnt = 0;
 
        int left = 0, right = s - 1;
 
        int mid = 0;
        while (left <= right) {
 
            mid = (left + right) / 2;
            
            if (v.at(mid) > input)
                right = mid - 1;
            else if (v.at(mid) <= input)
                left = mid + 1;    
        }
        cnt = left;
        
        cout << cnt << "\n";
    }
 
 
    return 0;
}