[PS] BOJ 10868 / 최솟값

Minjun Kim

09 Sep 2025 • 2 min read

Thumbnail: Photo by Jakub Dziubak (Unsplash)

문제 링크: https://www.acmicpc.net/problem/10868

세그먼트 트리를 활용하는 기본적인 문제입니다. 다만, 트리의 노드에 값을 어떻게 저장할지 고민이 필요했습니다.

풀이

세그먼트 트리?

세그먼트 트리에 대한 설명과 구간 합을 저장하는 세그먼트 이전 글을 참고해 주세요 😄

구간 합 대신에 최솟값 저장하기

이전에 구현했던 세그먼트 트리는 구간의 합을 저장했습니다. 이번 문제에서는 구간 내의 최솟값을 기록해주면 됩니다. 또, 주어지는 M개의 입력이 전부 세그먼트 트리에서 값을 조회하는 연산만 있으므로 update를 구현하지 않아도 됩니다.

def build_segment_tree(node, start, end):
    if start == end:
        tree[node] = arr[start]
    else:
        mid = (start + end) // 2
        build_segment_tree(node * 2, start, mid)
        build_segment_tree(node * 2 + 1, mid + 1, end)
        tree[node] = min(tree[node * 2], tree[node * 2 + 1])

트리 배열을 초기화하는 함수



def query_segment_tree(node, start, end, left, right):
    if start >= left and end <= right:
        return tree[node]
    elif start > right or end < left:
        return NUMBER_MAX
    else:
        mid = (start + end) // 2
        left_res = query_segment_tree(node * 2, start, mid, left, right)
        right_res = query_segment_tree(node * 2 + 1, mid + 1, end, left, right)
        return min(left_res, right_res)

def query(left, right):
    return query_segment_tree(1, 0, N - 1, left - 1, right - 1)

구간 내 최솟값을 구하는 함수

전체 코드

from math import ceil, log2

input = open(0).readline
NUMBER_MAX = 1_000_000_001

N, M = map(int, input().split())
arr = list(int(input()) for _ in range(N))
tree = [0] * (1 << ceil(log2(N)) + 1)

def build_segment_tree(node, start, end):
    if start == end:
        tree[node] = arr[start]
    else:
        mid = (start + end) // 2
        build_segment_tree(node * 2, start, mid)
        build_segment_tree(node * 2 + 1, mid + 1, end)
        tree[node] = min(tree[node * 2], tree[node * 2 + 1])

def query_segment_tree(node, start, end, left, right):
    if start >= left and end <= right:
        return tree[node]
    elif start > right or end < left:
        return NUMBER_MAX
    else:
        mid = (start + end) // 2
        left_res = query_segment_tree(node * 2, start, mid, left, right)
        right_res = query_segment_tree(node * 2 + 1, mid + 1, end, left, right)
        return min(left_res, right_res)

def query(left, right):
    return query_segment_tree(1, 0, N - 1, left - 1, right - 1)

build_segment_tree(1, 0, N - 1)

for _ in range(M):
    print(query(*map(int, input().split())))

solution.py