[BOJ 2357] 최솟값과 최댓값

2357번: 최솟값과 최댓값

 

1. 문제 설명

예를 들어 1번~10번 정수는 연두색 박스의 범위이고 최솟값은 5, 최댓값은 100이다.

또 다른 예로, 8번~10번 정수는 주황색 박스의 범위이고 최솟값은 5, 최댓값은 81이다.

 

2. 구현 아이디어 1 - 맞았습니다!!

Segment Tree를 사용하면 쉽게 풀 수 있는 문제이다. (대부분의 세그먼트 트리 문제가 세그먼트 트리를 구현만 하면 쉽게 풀리는 것 같다)

[C++] 세그먼트 트리의 개념과 구현

 

이전에 세그먼트 트리의 개념에 대해 정리한 적이 있는데, 세그먼트 트리는 구간합뿐만 아니라 구간의 최댓값/최솟값을 구할 때도 사용할 수 있다. 구간의 최댓값/최솟값을 구하는 알고리즘을 RMQ(Range Maximum/Minimum Query)라고 한다.

 

세그먼트 트리의 구현은 기본적으로 init, update, query(=find) 함수로 이루어져있는데, 이번 문제에서는 중간에 수가 변경되지 않으므로 update 함수가 필요 없다.

 

최솟값과 최댓값을 둘 다 구해야 하므로 minTree와 maxTree 2개의 세그먼트 트리가 필요하다.

initMin, initMax, findMin, findMax 총 4개의 함수를 구현했다.

init 함수와 find 함수는 내부 구현은 동일하고, min 함수를 사용하는지 max 함수를 사용하는지에만 차이가 있다.

#include <bits/stdc++.h>

using namespace std;

// 세그먼트 트리 생성
int initMin(int start, int end, int node, vector<int> &tree, vector<int> &a) {
    if (start == end) return tree[node] = a[start];

    int mid = (start + end) / 2;

    int left = node * 2;
    int right = node * 2 + 1;

    // 부모 노드 = 왼쪽 자식 노드의 데이터 + 오른쪽 자식 노드의 데이터
    return tree[node] = min(initMin(start, mid, left, tree, a), initMin(mid+1, end, right, tree, a));
}

int initMax(int start, int end, int node, vector<int> &tree, vector<int> &a) {
    if (start == end) return tree[node] = a[start];

    int mid = (start + end) / 2;

    int left = node * 2;
    int right = node * 2 + 1;

    // 부모 노드 = 왼쪽 자식 노드의 데이터 + 오른쪽 자식 노드의 데이터
    return tree[node] = max(initMax(start, mid, left, tree, a), initMax(mid+1, end, right, tree, a));
}

int findMin(int start, int end, int node, int left, int right, vector<int> &tree) {
    // 범위 밖
    if (left > end || right < start) return INT_MAX;

    // 범위 안
    if (left <= start && end <= right) return tree[node];

    int mid = (start + end) / 2;

    return min(findMin(start, mid, node*2, left, right, tree), findMin(mid+1, end, node*2+1, left, right, tree));
}

int findMax(int start, int end, int node, int left, int right, vector<int> &tree) {
    // 범위 밖
    if (left > end || right < start) return INT_MIN;

    // 범위 안
    if (left <= start && end <= right) return tree[node];

    int mid = (start + end) / 2;

    return max(findMax(start, mid, node*2, left, right, tree), findMax(mid+1, end, node*2+1, left, right, tree));
}

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

    int n, m;
    cin >> n >> m;

    vector<int> minTree = vector<int>(4*n);
    vector<int> maxTree = vector<int>(4*n);
    vector<int> arr = vector<int>(n);

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

    initMin(0, n-1, 1, minTree, arr);
    initMax(0, n-1, 1, maxTree, arr);

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;

        int mn = findMin(0, n-1, 1, a-1, b-1, minTree);
        int mx = findMax(0, n-1, 1, a-1, b-1, maxTree);

        cout << mn << " " << mx << "\n";
    }
}

 

처음에는 findMin, findMax 함수의 left, right 값으로 a-1, b-1를 대입해주어야 한다는 것을 주의하자.

정수를 담은 배열(=arr)의 인덱스는 0부터 시작하고, 문제에서 말하는 a번째는 1부터 시작하기 때문이다.