반응형

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

 

11003번: 최솟값 찾기

N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. 비재귀 세그먼트 트리를 이용하여 각 구간의 최솟값을 구해주고, 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int arr[10000001];
int N, L;
 
int getTree(int left, int right)
{
    left += N;
    right += N;
    int ret = 1000000000;
 
    while (left <= right) {
        if (left & 1) {
            ret = min(arr[left], ret);
            left += 1;
        }
        if (~right & 1) {
            ret = min(arr[right], ret);
            right -= 1;
        }
        left >>= 1;
        right >>= 1;
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> L;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[N + i];
    }
 
    for (int i = N - 1; i >= 1; i--) {
        arr[i] = min(arr[i << 1], arr[i << 1 | 1]);
    }
 
    for (int i = 0; i < N; i++) {
        cout << getTree(max(0, i - L + 1), i) << ' ';
    }
}
cs

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14419번 - Foehn Phenomena (C++)  (0) 2023.05.07
[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
[ 백준 ] 1395번 - 스위치 (C++)  (0) 2023.05.03
[ 백준 ] 9426번 - 중앙값 측정 (C++)  (0) 2023.05.02
[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01

+ Recent posts

티스토리툴바