[10868] 최솟값

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

10868 - 최솟값

본문

$N$($1 \leq N \leq 100\,000$)개의 정수들이 있을 때, $a$번째 정수부터 $b$번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 $a, b$의 쌍이 $M$($1 \leq M \leq 100\,000$)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 $a$번째라는 것은 입력되는 순서로 $a$번째라는 이야기이다. 예를 들어 $a=1, b=3$이라면 입력된 순서대로 $1$번, $2$번, $3$번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 $1$이상 $1\,000\,000\,000$이하의 값을 갖는다.

입력

첫째 줄에 $N, M$이 주어진다. 다음 $N$개의 줄에는 $N$개의 정수가 주어진다. 다음 $M$개의 줄에는 $a, b$의 쌍이 주어진다.

출력

$M$개의 줄에 입력받은 순서대로 각 $a, b$에 대한 답을 출력한다.

제한

시간 제한	메모리 제한
1sec	256MB

---

풀이

문제 자체에서 일반적인 탐색 알고리즘을 사용했을 때의 문제점을 제시하고 있다. 쿼리를 반복하는 것의 시간이 매우 오래 걸린다는 것. 다행히도 우리는 이것을 해결할 방법을 알고 있다. 바로 세그먼트 트리.

문제가 세그먼트 트리의 기본형인 만큼, 풀이과정은 생략한다.

• 참고 알고리즘 : 세그먼트 트리

코드

사용 언어 : C

최종 수정일 : 2023 / 10 / 13

#include <stdio.h>

#define MAX_IDX (int)(1e5 + 1)
const int root = 1;
const int INF = (int)(1e9 + 1);

int segtree[MAX_IDX * 4];
int arr[MAX_IDX];
int n, m;

#define min(a, b) (((a) > (b)) ? (b) : (a))

int segtree_init(int node, int start, int end) {
    if (start == end) {
        return segtree[node] = arr[start];
    }

    int lnode = segtree_init(node * 2, start, (start + end) / 2);
    int rnode = segtree_init(node * 2 + 1, (start + end) / 2 + 1, end);

    return segtree[node] = min(lnode, rnode);
}

int query(int node, int start, int end, int left, int right) {
    if (left > end || right < start) {
        return INF;
    } else if (left <= start && end <= right) {
        return segtree[node];
    }

    int lnode = query(node * 2, start, (start + end) / 2, left, right);
    int rnode = query(node * 2 + 1, (start + end) / 2 + 1, end, left, right);

    return min(lnode, rnode);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%d", arr + i);
    }

    segtree_init(root, 0, n - 1);

    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", query(root, 0, n - 1, a - 1, b - 1));
    }

    return 0;
}