BOJ 16510번 : Predictable Queue

문제

---

문제 풀이

문제를 보자마자 생각난 풀이는 당연히 바로 하나씩 누적해가면서 최선의 값을 찾는 것이었다. 하지만 해당 문제의 경우에는 입력 값의 범위가 넓어서 일일이 누적해서 찾는 것을 최대 200,000번 반복하다보면 어마어마한 시간이 걸린다. (당연히 시간초과가 남)

이분 탐색

1. 배열을 그냥 입력된 대로 넣는게 아니라 누적합 배열을 만든다
2. 입력 받은 시간으로 누적합 배열을 이분 탐색으로 빠르게 탐색해 답을 찾는다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<long long> v;
int n, m;

int binary(long long t, int start, int end) {
    if (start > end) { return start; }

    int mid = (start + end) / 2;

    if (v[mid] > t) { return binary(t, start, mid - 1); }
    else { return binary(t, mid + 1, end); }

    return start;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    long long work, time; // 벌여놓은 일 개수, 알아볼 시간 개수
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> work;
        if (i != 0) { work += v[i - 1]; }
        v.push_back(work);
    }

    for (int i = 0; i < m; i++) {
        cin >> time;
        cout << binary(time, 0, n - 1) << '\n';
    }

    return 0;
}

처음에는 모든 경우의 수를 아래 처럼 나눠서 모든 경우에 다 대응시켰다.
그랬더니 예제는 맞게 나오는데 자꾸 틀렸습니다가 뜨더라.

1. v[mid]와 같은 경우: 답 찾음!
2. v[mid]가 t보다 작은 경우:
   -- 2-0. mid가 마지막 인덱스인 경우: 답 찾음!
   -- 2-1. v[mid+1]도 t보다 작음: 오른쪽 부분 확인 (start = mid + 1)
   -- 2-2. v[mid+1]은 t보다 큼: 답 찾음!
3. v[mid]가 t보다 큰 경우: 왼쪽 부분 확인 (end = mid - 1)

아직도 왜 틀렸는지는 모르겠다. 백준은 반례가 너무 적음...

int binary(int t, int start, int end) {
    if (start > end) { return 0; }

    int mid = (start + end) / 2;

    if (v[mid] == t) { return mid; }
    else if (v[mid] < t) {
        if (mid == n - 1) { return mid; }

        if (v[mid + 1] < t) { return binary(t, mid + 1, end); }
        else if (v[mid + 1] > t) { return mid; }
    }
    else { return binary(t, start, mid - 1); }

    return 0;
}

바보같이 n이랑 m을 헷갈려써서 두 번 더 틀림...