[BOJ/Platinum 5] 백준 1306 달려라 홍준(C++)

문제 링크

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

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

알고리즘 분류

• 자료 구조

풀이

빛의 세기가 최대 100만까지 주어지고, 최댓값 찾기를 거의 100만번을 수행해야 하므로 세그먼트 트리를 이용한다면 시간 제한 안에 문제를 해결할 수 있다 최댓값을 찾기 위한 세그먼트 트리를 구현하고, M번째부터 N-M+1번째까지의 수를 중심으로 양 옆 M-1개까지의 수를 범위로 하여 해당 범위의 최댓값을 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1000001
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
int Tree_Height, Tree_Size;
vector<int> SegTree;
int MAP[MAX];

void Input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> MAP[i];
	}
}

int Make_SegTree(int Node, int Start, int End) {
	if (Start == End) {
		return SegTree[Node] = MAP[Start];
	}
	int MID = (Start + End) / 2;
	return SegTree[Node] = max(Make_SegTree(Node * 2, Start, MID), Make_SegTree(Node * 2 + 1, MID + 1, End));
}

int Find_Max_Value(int Node, int Start, int End, int Left, int Right) {
	if ((Left > End) || (Start > Right)) {
		return -1;
	}
	if ((Left <= Start) && (End <= Right)) {
		return SegTree[Node];
	}
	int MID = (Start + End) / 2;
	return max(Find_Max_Value(Node * 2, Start, MID, Left, Right), Find_Max_Value(Node * 2 + 1, MID + 1, End, Left, Right));
}

void Settings() {
	Tree_Height = (int)ceil(log2(N));
	Tree_Size = (1 << (Tree_Height + 1));
	SegTree.resize(Tree_Size);
	Make_SegTree(1, 0, N - 1);
}

void Find_Answer() {
	for (int i = M - 1; i <= (N - M); i++) {
		cout << Find_Max_Value(1, 0, N - 1, i - (M - 1), i + (M - 1)) << " ";
	}
	cout << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}