[ BOJ ] 1306 : 달려라 홍준 ( PLATINUM 5 ) / C

문제

홍준이는 러너이다. 그런데 어쩌다 보니 아무리 뛰어도 뛰어도 속도가 변하지 않는다. 1초에 딱 1칸을 움직인다.

그런데 홍준이가 뛰는 코스는 광고판으로 가득하다. 광고판은 빛의 세기가 다른데, 홍준이는 자신이 볼 수 있는 광고판들 중에서 가장 강렬한 빛의 광고판만이 눈에 들어온다.

홍준이는 눈이 안좋기 때문에 빛의 세기가 강한 지점에서는 안경을 쓰고 뛰려한다. 그래서 알아야 할 것이, 뛰어가면서 보이는 광고판의 빛의 세기를 알고 싶다.

홍준이가 뛰어갈 때, 1초마다 보이는 광고판의 빛의 세기를 출력하여라.

입력

첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 줄에는 각각 칸에 있는 광고판들의 빛의 세기가 주어진다. 빛의 세기는 1,000,000을 넘지 않는 자연수이다.

홍준이는 언제나 광고판을 2M-1개 보면서 뛰고 싶기 때문에(중심으로) M번째 칸에서 뛰기 시작해서 N-M+1번째 칸에서 멈춘다고 가정하자.

출력

뛰면서 보이는 광고판의 세기를 출력한다.

풀이 과정

최댓값 세그먼트 트리에 슬라이딩 윈도우 기법을 적용하면 간단하게 풀리는 문제이다. ( 이게 플레티넘 5? )

#include <stdio.h>
#define SIZE 1000001
typedef long long LL;

int arr[SIZE];
LL tree[SIZE * 4] = {0,};

LL max(LL l, LL r) {
	if (l > r) return l;
	else return r;
}

void init(int start, int end, int idx) {
	if (start == end) {
		tree[idx] = arr[start];
		return;
	}
	
	int mid = (start + end) / 2;
	init(start, mid, idx * 2);
	init(mid + 1, end, idx * 2 + 1);
	tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
}

LL interval_max(int start, int end, int idx, int left, int right) {
	if (end < left || right < start) return -1;
	if (left <= start && end <= right) return tree[idx];

	int mid = (start + end) / 2;
	return max(interval_max(start, mid, idx * 2, left, right), interval_max(mid + 1, end, idx * 2 + 1, left, right));
}

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) scanf("%d", &arr[i]);

	init(0, n - 1, 1);
    
	for (int i = m - 1; i < n - m + 1; i++) {
		printf("%lld ", interval_max(0, n - 1, 1, i - (m-1), i + (m-1)));
	}
	return 0;
}