[Gold / 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에 대한 답을 출력한다.

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <cmath>
#include <limits.h>
#include <algorithm>
using namespace std;

vector<int> tree;

void setTree(int i) { // 총 노드 수
	while(i != 1) {
		if(tree[i / 2] > tree[i]) {
			tree[i / 2] = tree[i]; // 더 작은 값으로
		}
		i--;
	}
}
		
int getMin(int s, int e) { // 구간 내 최솟값 구하기
	int Min = INT_MAX;
	
	while(s <= e) {
		if(s % 2 == 1) { // s가 홀수면
			Min = min(Min, tree[s]);
			s++;
		}
		s = s / 2; // 부모로 이동
		if(e % 2 == 0) { // e가 짝수면
			Min = min(Min, tree[e]);
			e--;
		}
		e = e / 2;
	}
	return Min;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	int treeHeight = 0;
	int length = n; 
	
	while(length != 0) {
		length /= 2;
		treeHeight++;
	}
	int treeSize = pow(2, treeHeight + 1);
	int leftNodeStart = (treeSize / 2) - 1;
	
	// 트리 초기화
	tree.resize(treeSize);
	fill(tree.begin(), tree.end(), INT_MAX); // 최소 구하기 -> min 사용 할거니까
	
	// input : n
	for(int i = leftNodeStart + 1; i <= leftNodeStart + n; i++) {
		cin >> tree[i];
	}
	setTree(treeSize - 1); // 트리 만들기
	
	// input : m
	for(int i = 0; i < m; i++) {
		int s, e;
		cin >> s >> e;
		s += leftNodeStart;
		e += leftNodeStart;
		cout << getMin(s, e) << "\n";
	}
	return 0;
}