[백준 19646번] [세그먼트 트리 / 이분 탐색] Random Generator

Approach

"dp[i] : i번째 수까지 활용했을 때 존재하는 수"라고 잡아서 dp로 풀 수 있을 것처럼 보이지만

이 문제는 업데이트가 자주 나오고 있는 상황이므로, dp 값이 계속 바뀐다.

따라서 이 문제는 dp로 풀 수 없다.

 

업데이트가 자주되고 특정 숫자까지 사용하였을 때 개수가 중요하므로

구간합과 쿼리로 문제 상황을 이해할 수 있다. 해당하는 숫자까지 사용했을 때의 개수가 주어진 숫자보다 더 큰 것 중 가장 작은 것을 찾아야 하는 상황이다. 특정 임계점을 기준으로 해당 경향성이 갈리므로 이분탐색을 활용해주면 된다.

 

따라서 시간 복잡도는, 이분탐색에서 logN이고 세그먼트에서 탐색이 logN, 마지막으로 모든 숫자에 대해 해당 작업을 처리해야하므로 N을 곱해서 $O(N(lgN)^2)$이다.

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int seg[800000];
int data_value[200001];

void update(int node_index, int node_left, int node_right, int index, int value){
    if(index < node_left || index > node_right) return; // Out of bound

    if(node_left == node_right){
        seg[node_index] += value;
        return;
    }
    else{
        int mid = (node_left + node_right) / 2;
        update(node_index * 2, node_left, mid, index, value);
        update(node_index * 2 + 1, mid + 1, node_right, index, value);
        seg[node_index] += value;
        return;
    }
}

int query(int node_index, int node_left, int node_right, int end_index){
    int start_index = 1;
    if(end_index < node_left || node_right < start_index) return 0;
    else if(start_index <= node_left && node_right <= end_index) return seg[node_index]; // 전부 다 포함

    int mid = (node_left + node_right) / 2;
    return query(node_index * 2, node_left, mid, end_index) +
           query(node_index * 2 + 1, mid + 1, node_right, end_index);
}

int main(void){
    fastio;
    memset(seg, 0, sizeof(seg));
    memset(data_value, 0, sizeof(data_value));

    int N;
    cin >> N;

    for(int i = 1; i <= N; i++){
        int t;
        cin >> t;
        update(1, 1, N, i, t);
        data_value[i] = t;
    }

    for(int i = 0; i < N; i++){
        int cmp;
        cin >> cmp;

        int start = 1;
        int end = N + 1;
        while(start < end){
            int mid = (start + end) / 2;
            if(query(1, 1, N, mid) >= cmp){
                end = mid;
            }
            else start = mid + 1;
        }
        
        cout << start << " ";
        update(1, 1, N, start, -data_value[start]);
    }
    cout << "\n";
    return 0;
}