백준 2805 파이썬

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

처음 구현한 방법 : 시간 초과가 날걸 알면서도 다른 방법이 생각나지 않아 일단 코드를 작성하고 제출했다. 예제 코드는 돌아가지만 제출을 하니 역시 시간초과가 발생했다.

n, m = map(int, input().split())
h = list(map(int,input().split()))
maxchecker = max(h) - 1
minchekcer = min(h) + 1
len = maxchecker - minchekcer
total = 0


for i in range(len):
    for j in range(n):
        if(h[j] - maxchecker >= 0):
            total += h[j] - maxchecker
    if(total >= m):
        print(maxchecker)
        break
    maxchecker -= 1
    total = 0

 

시간초과가 뜨면 어떤 구현 방법을 써서 구현해야 할지 다시 생각해봐야 한다. 이렇게 크기를 비교하며 반복하는 구조에서는 주로 이분탐색을 이용하면 시간초과 문제를 해결할 수 있다.

이분탐색(이진탐색? https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89) 

n, m = map(int, input().split())
trees = list(map(int,input().split()))
startPoint = 1
endPoint = max(trees)
total = 0

while startPoint <= endPoint:
    mid = (startPoint + endPoint) // 2
    total = 0
    for i in trees:
        if i >= mid:
            total += i - mid
    
    if total >= m:
        startPoint = mid + 1
    else:
        endPoint = mid - 1
print(endPoint)

 

 

오랜만에 문제를 풀다 보니 어떤 문제가 발생했을 때 어떤 방법으로 접근하는지에 대해서 감을 다 잃었다는 게 느껴졌다. 그래도 꾸준히 하다 보면 금방 감을 잡을 거라고 믿고 다시 파이팅!