[10868] 최소값

• 입력: 정수 N, M(1 ≤ N, M  ≤ 100,000), 정수 N개, M개의 (a, b) 쌍 (각 정수들 1이상 1,000,000,000 이하)
• 출력: M개의 줄에 입력받은 순서대로 각 a~b번째 숫자 중 최솟값 출력
• 소스

#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cmath> #include <vector> #define MAX 1000*1000*1000 + 1 using namespace std; int min(int a, int b) { return (a < b ? a : b); } int init(vector<int>& tree, vector<int>&arr, int node, int start, int end) { if (start == end) return tree[node] = arr[start]; else return tree[node] = min(init(tree, arr, node * 2, start, (start + end) / 2), init(tree, arr, node * 2 + 1, (start + end) / 2 + 1, end)); } int retMinimun(vector<int>& tree, int node, int start, int end, int left, int right) { if (left > end || right < start) return MAX; if (left <= start && end <= right) return tree[node]; return min(retMinimun(tree, node * 2, start, (start + end) / 2, left, right), retMinimun(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right)); } int main() { int N, M; scanf("%d %d", &N, &M); vector<int> arr(N); int h = (int)ceil(log2(N)); int tree_size = (1 << (h + 1)); vector<int> tree(tree_size, MAX); for (int i = 0; i < N; i++) scanf("%d", &arr[i]); init(tree, arr, 1, 0, N - 1); int a, b; for (int i = 0; i < M; i++) { scanf("%d %d", &a, &b); printf("%d\n",retMinimun(tree, 1, 0, N - 1, a - 1, b - 1)); } return 0; }

• 소스 설명:

세그먼트 트리를 이용해서 문제를 풀었다.

init 함수에서 입력받은 정수들을 tree 배열에다가 각각의 최솟값을 기록한다.

retMinimum 은 입력받은 a~b구간에 최솟값을 리턴하다.

• 참고사이트: https://www.acmicpc.net/problem/10868

• 세그먼트 트리가 종종 문제로 나오는데 처음 풀어봤다. 연습용으로 두어개 더 풀 예정이다.