[BOJ] 10868 - 최솟값 (Python)

 

 

아이디어

 

세그먼트 트리로 특정 범위에서의 최솟값을 저장해두고 찾는 범위에 대해 빠르게 처리한다.

 

 

풀이

 

2357번 최솟값과 최댓값 문제에서 최솟값만 고려하여 풀 수 있다.

 

N보다 큰 2의 거듭제곱 중 가장 작은 값의 두 배 크기로 0으로 채워진 리스트 tree를 만든다.

tree의 리프 노드들에 N개의 수를 입력 받고, for문에서 tree의 부모 노드들을 두 자식 노드 중 더 작은 값으로 저장한다.

값이 0인 자식 노드가 포함되어 있는 경우 부모 노드에 0이 아닌 자식 노드의 값을 저장한다.

M개의 a, b 쌍을 입력 받아 함수 find를 호출하여 반환된 최솟값을 출력한다.

 

함수 find에서는 리프 노드에서부터 차례로 부모 노드로 올라가며 최솟값을 res에 저장한다.

s%2 == 1 또는 e%2 == 0처럼 두 자식 노드 중 한 노드만 포함되어 있는 경우 그 값을 res와 비교하여 더 작으면 갱신하고,

해당 노드의 부모 노드로 올라가지 않도록 옆 노드로 인덱스를 이동한다.

 

import sys

input = sys.stdin.readline

def find(s, e):
    res = tree[s]
    while s <= e:
        if s%2:
            if tree[s] < res:
                res = tree[s]
            s += 1
        if e%2 == 0:
            if tree[e] < res:
                res = tree[e]
            e -= 1
        s, e = s//2, e//2
    return res

N, M = map(int, input().split())
n = 1
while n < N:
    n *= 2
tree = [0]*(n*2)
for i in range(N):
    tree[n+i] = int(input())
for i in range(n-1, 0, -1):
    if tree[i*2] and tree[i*2+1]:
        tree[i] = min(tree[i*2], tree[i*2+1])
    else:
        tree[i] = max(tree[i*2], tree[i*2+1])
for _ in range(M):
    a, b = map(int, input().split())
    print(find(a+n-1, b+n-1))