c언어 10868번 최솟값 (백준)

#include <stdio.h>
#define M 1000000001 //최대 입력값보다 더 큰 수를 치환메크로로 만듭니다.

int a[100001] = {}; //요소들 담을 배열
int tree[400001] = {}; //트리를 담을 배열

int min(int x, int y) {return (x<y) ? x : y;} //더 작은 것 반환

int init(int start, int end, int node) { //트리 배열 초기화하기
	if(start == end) return tree[node] = a[start]; //구간의 크기가 1 이므로, 최솟값은 자기 자신이다.
	int mid = (start+end)/2;
	return tree[node] = min(init(start, mid, node*2), init(mid+1, end, node*2+1)); //최솟값 대입
}

int find(int start, int end, int node, int left, int right) { //구간의 최솟값 찾기
	if(start > right || end < left) return M; //찾고 있는 범위가 아닐 경우
	if(left <= start && end <= right) return tree[node]; //찾고있는 범위안에 포함된경우
    //찾고 있는 범위와 걸친경우 (포함되진 않으나, 겹침)
	int mid = (start+end)/2;
	return min(find(start, mid, node*2, left, right), find(mid+1, end, node*2+1, left, right)); //최솟값 대입
}

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d", &a[i]); //요소 입력 받기
	init(1, n, 1); //트리 초기화
	
	while(m--) {
		int a, b;
		scanf("%d %d", &a, &b);
		printf("%d\n", find(1, n, 1, a, b)); //구간의 최솟값 찾기
	}
}

풀이 : segment tree

 

문제에서, 수정은 존재하지 않으며, 구간의 최솟값을 물어보고 있습니다.

그러므로 세그먼트 트리에 최솟값을 넣어 놓으면, 구간의 최솟값을 O(logn) 의 속도로 찾을 수 있습니다.

 

1. 요소를 저장할 배열, 트리를 만들 배열을 생성합니다.

2. 입력받은 요소들로 트리를 초기화 합니다.

3. m만큼 구간의 최솟값을 찾아서 출력합니다.

 

주의 : 이 코드는 느립니다!

 

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

10868번: 최솟값