[백준 10868] 최솟값 (C++)

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

 

문제

---

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

입력

---

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

출력

---

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 출력한다.

 

문제 풀이

---

세그먼트 트리 문제.

 

기본 세그먼트 트리는 특정 노드까지의 합을 구해 저장하는 트리였다면 이 문제는 최솟값을 저장하는 트리를 만들면 된다.

초기화 시 left=right일 때 세그먼트 트리의 값을 원래 배열에서 해당 노드의 번호를 찾아 초기화해주고, 이외에는 범위를 반으로 나누어 재귀적으로 초기화를 진행한다. 기본 세그먼트 트리가 자식 노드의 합으로 값이 정해졌으므로, 최솟값을 저장하는 세그먼트 트리는 두 자식 노드 중 더 작은 것을 저장하도록 구현해야 하는 것을 떠올릴 수 있다.

 

아래는 코드.

#include <iostream>
#include <cmath>
using namespace std;
int* arr;
int* segTree;

int init(int left, int right, int nodeNum)
{
	if (left == right)
	{
		return segTree[nodeNum] = arr[left];
	}
	else
	{
		int mid = (left + right) / 2;
		segTree[nodeNum] = min(init(left, mid, nodeNum * 2), init(mid + 1, right, nodeNum * 2 + 1));
		return segTree[nodeNum];
	}
}

int search(int start, int end, int left, int right, int nodeNum)
{
	if (start > right || end < left)
	{
		return 1000000001;
	}
	else if (start <= left && right <= end)
	{
		return segTree[nodeNum];
	}
	else
	{
		int mid = (left + right) / 2;
		return min(search(start, end, left, mid, nodeNum * 2), search(start, end, mid + 1, right, nodeNum * 2 + 1));
	}
}

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

	int N, M;
	int a, b;
	cin >> N>>M;
	arr = new int[N];
	segTree = new int[4 * N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	init(0, N - 1, 1);
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		cout<<search(a-1, b-1, 0, N - 1, 1)<<"\n";
	}
	return 0;
}