반응형
https://www.acmicpc.net/problem/1306
1306번: 달려라 홍준
첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/51
[ 자료구조 ] 세그먼트 트리 (Segment Tree)
1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1
rudalsd.tistory.com
1. 각각의 노드에 해당 범위의 최댓값을 저장하고, for문을 통해 인덱스를 슬라이싱 하면서 원하는 범위에서의 최댓값을 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include<iostream> #include<cmath> using namespace std; int N, M; int segTree[2111111]; int arr[1000001]; void makeTree(int node, int s, int e) { if (s == e) { segTree[node] = arr[s]; return; } int m = (s + e) / 2; makeTree(node * 2, s, m); makeTree(node * 2 + 1, m + 1, e); segTree[node] = max(segTree[node * 2], segTree[node * 2 + 1]); } int getTree(int node, int s, int e, int sidx, int eidx) { if (eidx < s || e < sidx) return 0; if (sidx <= s && e <= eidx) return segTree[node]; int m = (s + e) / 2; int left = getTree(node * 2, s, m, sidx, eidx); int right = getTree(node * 2 + 1, m + 1, e, sidx, eidx); return max(left, right); } int main() { scanf("%d %d", &N, &M); for (int i = 1; i <= N; i++) { scanf("%d", &arr[i]); } makeTree(1, 1, N); for (int i = M; i <= N - M + 1; i++) { printf("%d\n", getTree(1, 1, N, i - (M - 1), i + M - 1)); } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2230번 - 수 고르기 (C++) (0) | 2023.04.08 |
|---|---|
| [ 백준 ] 17400번 - 깃발춤 (C++) (0) | 2023.04.07 |
| [ 백준 ] 17845번 - 수강 과목 (C++) (0) | 2023.04.05 |
| [ 백준 ] 1321번 - 군인 (C++) (0) | 2023.04.04 |
| [ 백준 ] 14728번 - 벼락치기 (C++) (0) | 2023.04.03 |