BOJ 10868 최솟값

최솟값 [골드 1]

---

문제 링크

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

풀이

세그먼트 트리를 활용하여 문제를 푼다. 매번 주어진 범위를 구해 문제를 풀면 O(NM)의 시간복잡도를 갖기 때문에 시간 초과가 난다. 세그먼트 트리의 경우 범위 조회에는 O(lgN), 위 문제의 경우 업데이트는 없지만 O(lgN)의 시간 복잡도를 갖는다. 때문에 1초라는 시간 제한을 넘기지 않고 통과할 수 있다.

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

int init(vector<int> &a, vector<int> &tree, int node, int start, int end) {
    if(start == end) {	// leaf node
        return tree[node] = a[start];
    }
    else {	// node * 2 : 왼쪽 자식, node * 2 + 1 : 오른쪽 자식
        int mid = (start + end) / 2;
        return tree[node] = min(init(a, tree, node * 2, start, mid), init(a, tree, node * 2 + 1, mid + 1, end));
    }
}

// tree[node]는 start ~ end까지의 min 값을 갖고 있다.
int get(vector<int> &tree, int node, int start, int end, int left, int right) {
    if(left > end || right < start) {	// tree[node]의 범위를 벗어남
        return 1e9;
    }
    if(left <= start && end <= right) {	// 구하고자 하는 범위가 tree[node]를 완전히 포함하는 경우
        return tree[node];
    }
	
    // tree[node]가 left ~ right 일부를 포함하는 경우. 재귀를 통해 구한다.
    int mid = (start + end) / 2;
    return min(get(tree, node * 2, start , mid, left, right), get(tree, node*2+1, mid+1, end, left, right));
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int N, M, a, b;

    cin >> N >> M;
    vector<int> A(N);

    int h = (int)(ceil(log2(N)));
    int tree_size = 1 << (h + 1);
    vector<int> tree(tree_size);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    init(A, tree, 1, 0, N - 1);

    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        cout << get(tree, 1, 0, N - 1, a - 1, b - 1) << "\n";
    }

    return 0;
}