[백준] 10868번 - 최솟값

문제 분석

세그 먼트 트리의 개념을 이용해서, 원하는 구간의 최솟값을 구할 수 있다.
주어지는 N개의 값들을 리프노드에 저장하고, 최솟값을 만족하도록 위로 올라오면서, 최솟값 트리의 형태로 만들어준다.
그 후, 원하는 구간을 찾아 올라오면서 최솟값을 얻어내면 된다.

소스 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
treeHeight = 0

while pow(2, treeHeight) < N:
    treeHeight += 1

arr = [sys.maxsize] * pow(2, treeHeight + 1)

for i in range(pow(2, treeHeight), pow(2, treeHeight) + N):
    arr[i] = int(input())
for i in range(pow(2, treeHeight) - 1, 0, -1):
    arr[i] = min(arr[2*i], arr[2*i + 1])


def getIdx(idx):
    global treeHeight
    return idx + pow(2, treeHeight) - 1


def getMin(start, end):
    result = []
    startIdx = getIdx(start)
    endIdx = getIdx(end)
    while startIdx <= endIdx:
        if startIdx % 2 == 1:
            result.append(arr[startIdx])
        if endIdx % 2 == 0:
            result.append(arr[endIdx])
        startIdx = (startIdx + 1) // 2
        endIdx = (endIdx - 1) // 2
    return min(result)


for _ in range(M):
    s, e = map(int, input().split())
    print(getMin(s, e))