BOJ 백준 10868 : 최솟값

시작하면서

　이번 문제는 세그먼트 트리(Segment Tree) 문제이다.

BOJ 10868 - 최솟값

​

문제 이해

​ 해당 문제는 세그먼트 트리의 기본 문제이다. 세그먼트 트리 개념 <- 해당 링크대로 공부하고 풀면 풀린다.

​ 주의해야할 점은 input의 수가 굉장히 많으니 c++을 사용한다면 cync를 꺼주어야한다.

​

해결

#include <iostream>
#include <vector>
#include <math.h>
#include <limits.h>

using namespace std;

// 1. 배열의 인덱스 번호는 1부터 시작
// 2. 왼쪽 자식은 2 * index
// 3. 오른쪽 자식은 2 * index + 1

int InitSegmentTree(vector<int>& arr, vector<int>& segmentTree, int node, int start, int end)
{
	// 현재 노드가 리프 노드인 경우, 배열의 그 원소를 가져야 함
	if (start == end)
		return segmentTree[node] = arr[start];

	int mid = (start + end) * 0.5f;

	int left = InitSegmentTree(arr, segmentTree, node * 2, start, mid);
	int right = InitSegmentTree(arr, segmentTree, node * 2 + 1, mid + 1, end);

	segmentTree[node] = min(left, right);

	return segmentTree[node];
}

int QuerySegmentTree(vector<int>& segmentTree, int node, int start, int end, int left, int right)
{
	// 1. [start, end] 앞 뒤에 [left, right]가 있는 경우
	if (left > end || right < start)
		return INT_MAX;

	// 2. [start, end]가 [left, right]에 포함되는 경우
	if (left <= start && end <= right)
		return segmentTree[node];

	// 3. 나머지 경우
	int mid = (start + end) * 0.5f;

	int l = QuerySegmentTree(segmentTree, node * 2, start, mid, left, right);
	int r = QuerySegmentTree(segmentTree, node * 2 + 1, mid + 1, end, left, right);
	int minimum = min(l, r);

	return minimum;
}

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

	vector<int> v;
	vector<int> segmentTree;
	int N, M;

	cin >> N >> M;

	segmentTree.resize(N * 4);

	v.resize(N + 1);
	for (int i = 0; i < N; i++)
	{
		cin >> v[i];
	}

	InitSegmentTree(v, segmentTree, 1, 0, N - 1);

	for (int i = 0; i < M; i++)
	{
		int a, b;

		cin >> a >> b;

		cout << QuerySegmentTree(segmentTree, 1, 0, N - 1, a - 1, b - 1) << "\n";
	}

	return 0;
}