백준 10868 - 최솟값(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10868

10868번: 최솟값

세그먼트 트리를 이용한 문제입니다.

주어진 범위 안에서 가장 작은 값을 찾는 문제입니다.
일반적인 방법으로는, 배열을 for문으로 탐색 후 범위 안에 속한 값을 전부 비교해주게 됩니다.
하지만, 배열의 크기가 10^5이며, 주어지는 정수 쌍이 10^5이기에 시간 초과가 됩니다.

따라서, 세그먼트 트리를 이용해 일정 범위에서의 최솟값을 저장해주는 방법을 사용하면 됩니다.
세그먼트 트리를 이용해 최솟값을 저장하는 방법을 구현한다면, 나머지는 범위를 양쪽으로 나눠가면서 최솟값을 찾아주면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>

using namespace std;

int N, M;
int index[100001];
vector<long long> Tree;
vector<int> Min_tree;

long long segment_tree(int node, int st, int fin){
	if(st == fin) {
		Min_tree[node] = index[st];
		return Tree[node] = index[st];
	}
	int mid = (st + fin) / 2;
	long long left_sum = segment_tree(node * 2, st, mid);
	long long right_sum = segment_tree(node * 2 + 1, mid + 1, fin);
	Min_tree[node] = min(Min_tree[node  * 2], Min_tree[node * 2 + 1]);
	return Tree[node] = (left_sum + right_sum);
}

int check_tree(int node, int st, int fin, int left, int right){
	if(right < st || left > fin) return INT_MAX;
	if(left <= st && right >= fin) return Min_tree[node];
	int mid = (st + fin) / 2;
	int left_value = check_tree(node * 2, st, mid, left, right);
	int right_value = check_tree(node * 2 + 1, mid + 1, fin, left, right);
	return min(left_value, right_value);
}

void solve(){
	int height = ceil(log2(N));
	Tree.resize(1 << (height + 1));
	Min_tree.resize(1 << (height + 1));
	segment_tree(1, 0, N - 1);
	int x, y;
	for(int i = 1; i <= M; i++){
		scanf("%d %d", &x, &y);
		cout << check_tree(1, 0, N - 1, x - 1, y - 1) << "\n";
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 0; i < N; i++){
		scanf("%d", &index[i]);
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.