[BOJ | 백준] 10868번: 최솟값

by Kimcoding on 2020-03-01 04:28

in BOJ

문제 설명

BOJ 10868

구간 최솟값을 구하는 문제입니다.

풀이

RMQ (Range Minimum Query) 문제입니다.

N이 10만이라 완전 탐색으로 풀면 O(N2)이므로 제한 시간을 벗어납니다.

시간을 줄이기 위해 스파스 테이블을 쓰겠습니다.

시간 복잡도를 전처리 O(NlgN), 쿼리 O(1)로 할 수 있습니다.

스파스 테이블 (Sparse Table)

기본 코드를 구현한 문제라 링크로 대체하겠습니다!

소스 코드

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

int main() {
	FIO;
	int n, m; cin >> n >> m;
	int f[100005][17];
	memset(f, 0x3f, sizeof(f));
	FOR(i, 1, n) cin >> f[i][0];
	FOR(j, 1, 16) FOR(i, 1, n)
		if(i + (1 << (j - 1)) <= n) // 배열 인덱스 초과 처리
			f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
	while (m--) {
		int a, b; cin >> a >> b;
		int x = (int)log2(b - a + 1);
		cout << min(f[a][x], f[b - (1 << x) + 1][x]) << '\n';
	}
	return 0;
}