[백준] 10868번 최솟값 Python 해설

출처 : https://www.acmicpc.net/problem/10868

10868번: 최솟값

세그먼트 트리에 입문하기 위해 딱 좋은 문제라고 생각한다.

 

풀이

---

- Python 정답 코드

import sys
from math import ceil, log

input = sys.stdin.readline


def minimum(left, right, node_left, node_right, node_num):
    if left > node_right or right < node_left: return 1000000000
    if left <= node_left and right >= node_right: return arr[node_num]
    mid = (node_left + node_right)//2
    return min(minimum(left, right, node_left, mid, node_num*2),
     minimum(left, right, mid+1, node_right, node_num*2 + 1))

def init(size):
    for i in range(size - 1, 0, -1):
        arr[i] = min(arr[i*2], arr[i*2 + 1])
if __name__ == "__main__":
    N, M = map(int,input().split())

    size =  2**ceil(log(N,2))
    size_max = size * 2
    arr = [1000000000]*(size_max)
    for i in range(N):
        arr[size+i]=int(input())
    init(size)
    for _ in range(M):
        s, e = map(int,input().split())
        print(minimum(s-1, e-1, 0, size - 1,1))

init(size) 함수로 세그먼트의 구간 별 최솟값을 정리해준다.

중간에 값을 수정하지 않아도 되기 때문에 단순하게 초기화 함수와 구간의 값을 구하는 함수만 정의해 주면 된다.

 

결과 인증

---

문제 풀때 print()로 확인 작업을 하면서 푸는데, 실수로 지우지 않고 제출해버려서 또 출력 초과가 떴다.

끝까지 확인하고 항상 확인하자!