[ 백준 10868 ] 최솟값 (C++)

백준의 최솟값(10868) 문제이다.

[ 문제 바로가기  ]

[ 문제풀이 ]

단순하게 반복문을 통해서 최솟값을 찾는다면, 크기가 10만인 배열을 10만번 탐색하는 경우가 발생한다. 그렇게 되면 당연히

제한시간내에 통과하지 못하게 된다.

따라서 본인은 이 문제를 세그먼트 트리를 이용해서 구현해보았다. 아직 세그먼트 트리에 대해서 잘 모른다면 아래의 글을 읽고

오도록 하자.

[ 세그먼트 트리(SegmentTree) 알아보기(Click) ]

위의 세그먼트 트리에 대한 설명글은 '구간합'에 대한 개념으로 설명이 진행되어있다.

이 문제에서 세그먼트 트리를 적용하려면 약간만 바꿔주면 된다. 리프노드가 아닌 노드들에 대해서 해당 노드가 갖는 구간에 대한

연산 결과를 설정해주는 것이 아닌, 해당 구간에서 최솟값을 저장해 주면 된다.

또한, 특정 구간에서 최솟값을 찾는 연산을 진행할 때, "현재 노드가 내가 찾고자 하는 구간과 완전히 상관이 없는 구간을 갖는

노드" 일 때, 무한대의 값을 return 시켜주었다. 왜냐하면 어차피 찾고자 하는 값은 해당 구간에서의 최솟값을 찾는 것이고,

현재 노드가 해당 구간과 상관이 없는 구간을 포함하는 노드라면 이 구간에 대한 결과값은 정답에 영향을 미치면 안되기 때문에

무한대의 값을 return 시켜 주었다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
using namespace std;
 
int N, M;
vector<int> Arr;
vector<int> Segment_Tree;
vector<pair<int, int>> Cmd;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        int a; cin >> a;
        Arr.push_back(a);
    }
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        Cmd.push_back(make_pair(a, b));
    }
}
 
int Make_SegmentTree(int Node, int Start, int End)
{
    if (Start == End)
    {
        Segment_Tree[Node] = Arr[Start];
        return Segment_Tree[Node];
    }
 
    int Mid = (Start + End) / 2;
    int Left_Result = Make_SegmentTree(Node * 2, Start, Mid);
    int Right_Result = Make_SegmentTree(Node * 2 + 1, Mid + 1, End);
    Segment_Tree[Node] = Min(Left_Result, Right_Result);
    
    return Segment_Tree[Node];
}
 
int Query(int Node, int Start, int End, int Left, int Right)
{
    if (Right < Start || Left > End) return 2e9;
    if (Left <= Start && End <= Right) return Segment_Tree[Node];
    
    int Mid = (Start + End) / 2;
    int Left_Result = Query(Node * 2, Start, Mid, Left, Right);
    int Right_Result = Query(Node * 2 + 1, Mid + 1, End, Left, Right);
    return Min(Left_Result, Right_Result);
}
 
void Solution()
{
    int Tree_Height = ceil(log2(N));
    int Tree_Size = (1 << (Tree_Height + 1));
    Segment_Tree.resize(Tree_Size);
 
    Make_SegmentTree(1, 0, N - 1);
    for (int i = 0; i < Cmd.size(); i++)
    {
        int Index = Cmd[i].first - 1;
        int Index2 = Cmd[i].second - 1;
        
        cout << Query(1, 0, N - 1, Index, Index2) << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}