[알고리즘] 백준 1306번: 달려라 홍준 (C++), 슬라이딩 윈도우

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

1306번: 달려라 홍준

이번 문제는 문제에서 "가장 강렬한 빛의 광고판만이 눈에 들어온다."라는 말에서 구간 최댓값 세그 트리를 짜주면 되는 문제였다.

다만 어떤 구간인지에 관해서는 "슬라이딩 윈도우"라는 알고리즘(?)이 튀어나왔었다.

잠깐 구글링 해봤는데 알고리즘이라 하긴 그렇고, 테크닉(?) 같은 느낌이다.

따로 설명은 하지 않겠다. (나중에 어려움을 겪으면 그때 정리하겠다.)

시야 M이 주어지면 앞뒤로 M - 1, M + 1 사이의 빛을 볼 수 있다고 주어져있다. (1 ~ N 구간 사이)

그러면 탐색하는 구간은 이렇게 된다.

for (int i = m; i <= n - m + 1; i++) {
	cout << query(1, n, 1, i - m + 1, i + m - 1) << ' ';
}

M부터 시작하여 N - M + 1까지

쿼리의 범위는 [(i - (M - 1)), (i + (M - 1))]이렇게 된다.

문제에서 어차피 범위를 다 주기 때문에 어려움을 겪을 필요는 없다.

감이 잡히긴 하는데 조금 더 감을 잡을 시간이 필요하다.

[AC 코드]

#include <iostream>
#include <cmath>
#define MAX (1000000 + 1)
using namespace std;

int arr[MAX];
int sgTree[MAX * 4];
int n, m;

int sgInit(int start, int end, int node) {
	if (start == end) {
		return sgTree[node] = arr[start];
	}
	int mid = (start + end) >> 1;
	return sgTree[node] = max(sgInit(start, mid, node * 2), 
		sgInit(mid + 1, end, node * 2 + 1));
}

int query(int start, int end, int node, int left, int right) {
	if (start > right || end < left) return 0;
	if (left <= start && end <= right) return sgTree[node];
	int mid = (start + end) >> 1;
	return max(query(start, mid, node * 2, left, right), 
		query(mid + 1, end, node * 2 + 1, left, right));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	sgInit(1, n, 1);
	
	for (int i = m; i <= n - m + 1; i++) {
		cout << query(1, n, 1, i - m + 1, i + m - 1) << ' ';
	}
	return 0;
}