[BOJ] #2357 최솟값과 최댓값

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

---

시간초과가 나지 않게 세그먼트 트리를 사용해서 푸는 것이 핵심인 문제이다. 필자 또한 처음 풀때 별 생각없이 그냥 벡터 인덱스 접근해서 풀었다가 시간초과가 났다. 생각해보니, 입력값의 최대크기가 100,000이고 애초에 그렇게 해서 풀렸다면 골드1일 이유가 없다. 따라서 시간초과가 나지 않게 하기 위해서는 세그먼트 트리를 이용해서 풀어야한다.

보통 세그먼트 트리를 이용해서 푸는 문제들은 보통 구간 합을 구하거나 구성된 트리를 업데이트 하는 그런 문제들이 많은데 (BOJ #2042같은 문제가 대표적) 이 문제는 꼭 구간합을 구하는 문제가 아니더라도 세그먼트 트리를 활용하여 트리를 탐색해야 하는 문제이다.

예제로 주어진 입력에 대한 구간합 세그먼트 트리 구성

필자는 최솟값을 저장하는 트리와 최댓값을 저장하는 트리를 아예 따로 만들어, SOL 함수에서 boolean 타입 변수 flag로 최솟값을 출력해야 하는지, 최댓값을 출력해야 하는지 결정하여 출력하였다. 어차피 세그먼트트리 자체를 구성하는 매커니즘은 비슷하지만, 구간합을 구하는 것이 아닌 문제에서 어떻게 그를 처리해야하는지 학습할 수 있는 문제였다.

#include <iostream>
#include <climits>

#define MAX 100001
#define TREE_HEIGHT MAX*4

using namespace std;

int N,M;
long long arr[MAX];

long long segTree[TREE_HEIGHT];
int minTree[TREE_HEIGHT];
int maxTree[TREE_HEIGHT];

long long init(int start, int end, int node) {
    if (start == end) {
        minTree[node] = arr[start];
        maxTree[node] = arr[start];
        return segTree[node] = arr[start];
    }

    int mid = (start + end) / 2;

    long long tmp_left = init(start, mid, node*2);
    long long tmp_right = init(mid+1, end, node*2 + 1);
    minTree[node] = min(minTree[node*2], minTree[node*2 + 1]);
    maxTree[node] = max(maxTree[node*2], maxTree[node*2 + 1]);
    return segTree[node] = tmp_left + tmp_right;
}

int SOL(int start, int end, int node, int left, int right, bool flag) {
    if (left > end || right < start) {
        if (flag == false) return INT_MAX;
        else return -INT_MAX;
    }

    if (left <= start && right >= end) {
        if (flag == false) return minTree[node];
        else return maxTree[node];
    }

    int mid = (start + end) / 2;

    int tmp_left = SOL(start, mid, node*2, left, right, flag);
    int tmp_right = SOL(mid+1, end, node*2 + 1, left, right, flag);
    if (flag == false) return min(tmp_left, tmp_right);
    else return max(tmp_left, tmp_right);
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M;

    for (int i=0; i<N; i++) {
        cin >> arr[i];
    }

    init(0, N-1, 1);

    for (int i=0; i<M; i++) {
        int left, right;
        cin >> left >> right;

        left--; right--;

        int minTotal = SOL(0, N-1, 1, left, right, false);
        int maxTotal = SOL(0, N-1, 1, left, right, true);

        cout << minTotal << ' ' << maxTotal << '\n';
    }

    return 0;
}