[자료구조] 백준 10868번: 최솟값 (C++)

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

10868번: 최솟값

시간적인 측면에서 선형적인 구조로 최솟값을 구하면 안 된다.

세그먼트 트리를 써야 한다.

long long minTree[4 * MAX];
long long arr[MAX];

배열과 배열의 값들을 세그먼트 트리로 표현할 minTree를 선언해주고,

세그먼트 트리를 만드는 함수를 만들어준다.

//== Segment Tree INIT == (각 노드에 구간 최솟값)
long long init(int start, int end, int node) {
	if (start == end) {
		return minTree[node] = arr[start];
	}
	int mid = (start + end) / 2;
	return minTree[node] = min(init(start, mid, node * 2), init(mid + 1, end, node * 2 + 1));
}

여기서 쿼리가 주어지고, 함수를 돌릴 때 영역에 벗어난 부분은 무엇을 리턴해야 하는지가 포인트다.

long long findMinValue(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return INF; // 이 부분
	if (left <= start && right >= end) return minTree[node];
	int mid = (start + end) / 2;
	return min(findMinValue(start, mid, node * 2, left, right),
		findMinValue(mid + 1, end, node * 2 + 1, left, right));
}

마지막에 재귀에서 min(값, 값)을 해주는데 주석 처리된 부분에서 0을 리턴하면 최솟값들은 어떻게든 0이 나올 것이다.

그러므로 아예 말이 안 되게 INF(1000000000 + 1)를 리턴해주면 저건 무시해버리고, 다른 구간의 최솟값을 리턴한다.

 

[AC 코드]

ios_base::sync_with_stdio(false);
cin.tie(NULL);

이거 사용 안 하니까 시간 초과가 났었다.

#include <iostream>
#define MAX 100000 + 1
#define INF 1000000000 + 1
using namespace std;

long long minTree[4 * MAX];
long long arr[MAX];

int n, m;

//== Segment Tree INIT == (각 노드에 구간 최솟값)
long long init(int start, int end, int node) {
	if (start == end) {
		return minTree[node] = arr[start];
	}
	int mid = (start + end) / 2;
	return minTree[node] = min(init(start, mid, node * 2), init(mid + 1, end, node * 2 + 1));
}

long long findMinValue(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return INF;
	if (left <= start && right >= end) return minTree[node];
	int mid = (start + end) / 2;
	return min(findMinValue(start, mid, node * 2, left, right),
		findMinValue(mid + 1, end, node * 2 + 1, left, right));
}

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

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

	init(1, n, 1);

	for (int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		cout << findMinValue(1, n, 1, a, b) << '\n';
	}
}