072 최솟값

첫번째 코드

 

물론 코드는 책을 참고했지만, 이전에  풀어본 세그먼트 코드에서

해당 코드 부분마다 이해를 했기 때문에, 어느 코드를 빼야 하는지, 바꿔야 하는지에 대한 이해는 쉬웠다.

 

여러번 풀어보면 금방 풀 수 있을 것 같다.

하지만 코드를 혼자 작성하는 데에는 단계단계 생각하면서 작성해야 할 것이다.

또한 개념에서 암기를 해야 편한 부분이 있기 때문에 해당 부분도 이해해야 할 것이다.

 

나아가 함수가 많아지기 때문에 각 함수가 어디에 필요한지, 어떤 함수가 필요한지 익숙해져야 할 것이다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
treeHeight = 0
length = n

while length != 0:
    length //= 2
    treeHeight += 1

treeSize = 2 ** (treeHeight + 1)
leftNodeStartIndex = treeSize//2 - 1
tree = [sys.maxsize] * (treeSize + 1)

for i in range(leftNodeStartIndex + 1, leftNodeStartIndex + n + 1):
    tree[i] = int(input())

def setTree(i):
    while i != 1:
        if tree[i // 2] > tree[i]:
            tree[i // 2] = tree[i]
        i -= 1

setTree(treeSize - 1)

def getMin(s, e):
    Min = sys.maxsize
    while s <= e:
        if s % 2 == 1:
            Min = min(Min, tree[s])
            s += 1
        if e % 2 == 0:
            Min = min(Min, tree[e])
            e -= 1
        s = s // 2
        e = e // 2
    return Min

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

 

통과

괜찮아! 다음에 또 풀어보자 :) 어려운 문제잖앙

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/10868.%E2%80%85%EC%B5%9C%EC%86%9F%EA%B0%92

programmers/백준/Gold/10868. 최솟값 at main · ornni/programmers