[BOJ] #10868 최솟값

시간 제한	메모리 제한	정답 비율
1 초	256 MB	47.180%

10868번: 최솟값

 

문제

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 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에 대한 답을 출력한다.

 

해결

key point, 세그먼트 트리

• 세그먼트 트리를 구성할 트리의 높이를 구한다. → h
  • 리프 노드에 입력받은 수를 차례로 놓을 것이기 때문에 리프노드의 개수가 n보다 크게끔 while문을 활용하여 높이를 구해준다.
  • 리프 노드를 제외한 노드는 구간의 최솟값을 갖고 있는다.
• 해당 세그먼트 트리에서는 구간의 최솟값을 구해야 하기 때문에 INF 무한대 값으로 초기화 한다. → fill(seg.begin(), seg.end(), INF)
• udpate 함수는 i 위치에 num을 저장하는 것이고, 처음엔 i + h로 리프노드에 저장시킨 후에 /= 2를 하며 조상 노드로 올라가 구간의 최솟값을 저장한다.
• query 함수는 구간의 최솟값을 구하는 함수다.
  • l, r은 찾고자 하는 범위의 시작과 끝이고, num은 현재 보고 있는 노드 번호, nl, nr은 현재 보고 있는 범위의 시작과 끝이다.
  • 구간에 따라서 최솟값을 반환하거나, 무한대값을 반환하거나, 재귀함수를 통해 답을 구한다.

 

코드

메모리	시간
3280 KB	112 ms

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;
#define INF 1e9
int n, m, h = 1;
vector<ll> seg;
void update(int i, int num) {
    i += h;
    seg[i] = num;
    while (i > 1) {
        i /= 2;
        seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
    }
}
// l, r 찾는 범위, num 현재 노드 번호, nl, nr 현재 범위
ll query(int l, int r, int num, int nl, int nr) {
    if (l <= nl && nr <= r) return seg[num];
    if (nl > r || nr < l) return INF;
 
    int mid = (nl + nr) / 2;
    return min(query(l, r, num * 2, nl, mid), query(l, r, num * 2 + 1, mid + 1, nr));
}
 
int main() {
    scanf("%d%d", &n, &m);
    while (h < n) h <<= 1;
    seg.resize(h * 2);
    fill(seg.begin(), seg.end(), INF);
    for (int i = 0, a; i < n; i++) {
        scanf("%d", &a);
        update(i, a);
    }
    for (int i = 0, a, b; i < m; i++) {
        scanf("%d%d", &a, &b);
        printf("%lld\n", query(a, b, 1, 1, h));
    }
    return 0;
}