[백준 BOJ 10868] 최솟값

백준 링크

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

풀이

• 세그먼트 트리를 이용해 쿼리마다 범위 내의 최솟값을 구한다
• 세그먼트 트리 :  https://www.acmicpc.net/blog/view/9
  
  • 노드마다 노드 번호, 구간, 구간 내의 최솟값을 나타내며 실제로 tree배열에는 각 구간의 최솟값을 저장한다
  • init() :
    • 재귀로 1번 노드부터 하위 노드로 이동하면서 리프노드에 도달 시 범위가 실제 값을 나타내므로 값 저장
    • 올라오면서 자식 노드 2개의 최솟값을 부모에 저장 => 모든 범위의 최솟값을 저장한다
  • query(node, start, end, a, b):
    • 각 노드의 구간을 start, end가 나타내며 a, b는 최솟값을 찾고자 하는 범위이다
    • 현재 노드의 구간과 a,b구간이 겹치지 않을 경우 return 0
    • 현재 노드 구간이 a,b구간에 완전히 포함될 경우 return tree[node]
    • 나머지 경우에 대해서는 자식 노드 두개를 비교해서 최솟값 리턴

 

코드

#include<bits/stdc++.h>
using namespace std;

int tree[1000000],arr[100005],n,m;

void init(int node, int s, int e){
    if(s == e){
        tree[node] = arr[s];
    }
    else{
        init(node*2,s,(s+e)/2);
        init(node*2+1,(s+e)/2+1,e);
        tree[node] = min(tree[node*2], tree[node*2+1]);
    }
}

int query(int node, int s, int e, int a, int b){
    if(a>e || b<s) return 0;
    if(a<=s && e<=b) return tree[node];
    int l = query(node*2,s,(s+e)/2,a,b);
    int r = query(node*2+1,(s+e)/2+1,e,a,b);
    if(!l) return r;
    else if(!r) return l;
    else return min(l,r);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> arr[i];
    }
    init(1, 1, n);
    int a, b;
    while(m--){
        cin >> a >> b;
        cout << query(1,1,n,a,b) << '\n';
    }
}

개선점

• 트리를 저장하는 배열크기를 N의 값에 따라 범위에 맞춰 지정하면 메모리를 절약할 수 있다