[BOJ] 10868번 : 최솟값

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

10868번: 최솟값

 

segment tree 개념 문제이다. 입력과 출력도 int 범위 내이고, update도 없으므로 크게 어려운 것 없는 문제이다. 다만 최솟값이라는 특성 상 initializing을 할 때 min(init(범위1), init(범위2)) 로 tree 값을 정해주고, query가 주어졌을 때에도 min(query(범위1), query(범위2))와 같은 형식으로 리턴을 하되, 범위 바깥이라면 1,000,000,000 이상의 값을 리턴하여 이 값이 포함되지 않도록 한다. 

 

 

#include <iostream>
#include <math.h>
#include <vector>
#define MAX 2000000000
 
using namespace std;
 
const int max_n = 100500;
vector<int> arr={0};
vector<int> tree(max_n*4);
 
int init(int start, int end, int node) {
    if(start==end) return tree[node] = arr[start];
    int mid = (start+end)/2;
    return tree[node] = min(init(start,mid,node*2),init(mid+1,end,node*2+1));
}
 
int query(int start, int end, int node, int left, int right) {
    if(start>=left && end <= right) return tree[node];
    if(end<left || start > right) return MAX;
    int mid = (start+end)/2;
    return min(query(start,mid,node*2, left,right),query(mid+1,end,node*2+1,left,right));
}
 
int main ( void ) {
    cin.tie(NULL);cout.tie(NULL);ios_base::sync_with_stdio(false);
 
    int n, m, temp1, temp2;
    cin>>n>>m;
    for(int i = 1; i<= n;i++) {
        cin>>temp1;
        arr.emplace_back(temp1);
    }
    
    init(1,n,1);
    for(int i = 1; i<= m; i++) {
        cin>>temp1>>temp2;
        cout<<query(1,n,1,temp1,temp2)<<'\n';
    }
}

 

이 코드는 내 github에서도 확인할 수 있다.

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/10868/10868.cpp

GitHub - Jordano-Jackson/PS: Problem solving