[백준] 달려라 홍준 (1306번)

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1 복사

5 2 1 1 1 3 2

예제 출력 1 복사

1 3 3

---

세그먼트 트리 문제이다.

주어진 범위 내에서 가장 큰 값이 무엇인지만 구하면 된다.

세그먼트 트리에 대한건 내 블로그 기본 알고리즘 파트에 설명해놓았으니 참고하자.

기본 세그먼트 트리 구현에서 구간합이 아닌 max를 구한다는 점만 다르다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%8B%AC%EB%A0%A4%EB%9D%BC%20%ED%99%8D%EC%A4%80%20(1306%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
int p[1000001];
vector<int> range;

int init(int left, int right, int node) {
	if (left == right) return range[node] = p[left];
	int mid = (left + right) / 2;
	return range[node] = max(init(left, mid, node * 2),init(mid + 1, right, node * 2 + 1));
}

int query(int left, int right, int node, int nodeLeft, int nodeRight) {
	if (nodeRight < left || right < nodeLeft) return 0;
	if (left <= nodeLeft && nodeRight <= right) return range[node];
	int mid = (nodeLeft + nodeRight) / 2;
	return max(query(left, right, node * 2, nodeLeft, mid), (query(left, right, node * 2 + 1, mid + 1, nodeRight)));
}

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> p[i];
	range.resize(N * 4);
	init(0,N-1,1);
	for (int i = M - 1; i <= N - M + 1 - 1; i++) {
		int lo = i - M + 1;
		int hi = i + M - 1;
		cout << query(lo, hi, 1, 0, N - 1) << " ";
	}
}