[백준] 10868번 최솟값

Segment tree를 활용하는 법에 익숙해져보자!

문제

문제 풀이

이번 문제는 segment tree의 기본였던 구간 합 구하기 문제에서 조금 활용하여서 최솟값을 구하는 문제이다. 만약 Segment tree에 대해서 잘 모르겠다면 아래 링크의 문제를 먼저 풀어보거나 풀이과정을 보고 오는 것을 추천한다.

백준 구간합 구하기 2042: https://koreaygj.github.io/algorithm/bj2042/

구간합을 하는 문제와 다르게 구간의 최솟값을 구하는 것이기 때문에 재귀를 통해 더할 필요없이 min를 활용했다.

마지막으로 출력시에는 각각의 트리에서 구하고자 하는 구간에 해당하는 최댓값, 최솟값의 구간을 찾는 방식으로 출력했다.

---

전체코드 자세히 보기

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> min_tree(100005 * 4, 0);
vector<int> arr(1000005, 0);
int init_min(int start, int end, int node)
{
    if(start == end)
        return min_tree[node] = arr[start];
    int mid = (start + end) / 2;
    return min_tree[node] = min(init_min(start, mid, node * 2) , init_min(mid + 1, end, node * 2 + 1));
}
int find_min(int start, int end, int node, int left, int right)
{
    if(left > end || right < start)
        return 1000000005;
    if(left <= start && end <= right)
        return min_tree[node];
    int mid = (start + end) / 2;
    return min(find_min(start, mid, node * 2, left, right), find_min(mid + 1, end, node * 2 + 1, left, right));
}
int main(void){
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m;
    vector<pair<int, int>> input;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    init_min(1, n, 1);
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        input.push_back({a, b});
    }
    for(int i = 0; i < m; i++)
    {
        cout << find_min(1, n, 1, input[i].first, input[i].second) << "\n";
    }
}

---

문제 결과

문제 출처 https://www.acmicpc.net/problem/10868