백준 1306 c++ "달려라 홍준" -PlusUltraCode-

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

[필자 사고]

기본 세그먼트 트리를 구현할줄 알면 쉽게 풀 수 있는 문제이다.

쿼리에 사용할 인덱스 범위는 너 ... 등차수열 아니? 정도만 알고 있으면 쉽게 쿼리 인덱스를 구할 수 있다.

 

추가적으로 조심해야될 부분은 인덱스 1부터 넣기 때문에 이 부분 항상 생각하자ㅣ

초기화 배열을 arr.resize(N+1) **

 

[코드 해설]

1. 입력 처리 (Input 함수)

• N과 M: 배열의 크기 N과 구간 범위 M을 입력받습니다.
• arr 벡터 초기화: 1부터 N까지의 배열 값을 입력받아 저장합니다. 배열은 1-based index로 구성됩니다.

---

2. 세그먼트 트리 초기화 (Init_Tree 함수)

• 세그먼트 트리를 생성하며, 각 노드에 구간 내 최대값을 저장합니다.
• 재귀적인 구조:
  • start == end (리프 노드): 해당 위치의 값을 트리에 저장합니다.
  • 구간 분할: 구간 [start, end]를 절반으로 나누고, 좌측 (node * 2) 및 우측 (node * 2 + 1) 구간에 대해 재귀적으로 트리를 초기화합니다.
  • 병합 연산: 현재 노드에 좌측 및 우측 자식 노드의 최대값을 저장합니다.

---

3. 쿼리 처리 (Query 함수)

• 세그먼트 트리에서 특정 구간 [left, right]의 최대값을 반환합니다.
• 구간 관계 확인:
  • 완전 포함: 구간 [start, end]가 [left, right]에 완전히 포함되면, 해당 노드 값을 반환합니다.
  • 겹치지 않음: 구간이 겹치지 않으면 최소값(LONG_MIN)을 반환합니다.
  • 부분 겹침: 구간을 나누어 좌측 및 우측 자식 노드의 최대값을 구하고, 이를 병합하여 반환합니다.

---

4. 게임 시작 (Game_Start 함수)

• 세그먼트 트리 초기화: Init_Tree 함수를 호출하여 트리를 생성합니다.
• 구간 최대값 계산:
  • 인덱스 i가 [M, N - M + 1] 범위에 대해, 구간 [i - M + 1, i + M - 1] 내의 최대값을 계산합니다.
  • Query 함수 호출: 구간 내 최대값을 세그먼트 트리에서 빠르게 조회합니다.
• 결과 출력: 각 구간의 최대값을 출력합니다.

---

5. 메인 함수

• Input 함수로 입력값을 처리합니다.
• Game_Start 함수로 구간 최대값을 계산하여 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

vector<long> tree;
vector<long> arr;
int N, M;

void Input() {
	cin >> N >> M;
	arr.resize(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
}

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

	tree[node] = max(tree[node * 2] ,tree[node * 2 + 1]);
}

long Query(int node, int start, int end, int left, int right) {
	if (left <= start && end <= right) {
		return tree[node];
	}

	if (end < left || right < start) {
		return LONG_MIN;
	}

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

void Game_Start() {
	
	tree.resize(N * 4 + 1,LONG_MIN);
	Init_Tree(1, 1, N);

	for (int i = M; i <= N - M + 1; i++) {
		cout << Query(1, 1, N, i - M + 1, i+M-1) << '\n';
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	Game_Start();
}