[백준] 2805. 나무 자르기

문제

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

2805번: 나무 자르기

설계

- 처음에는 내음대로 풀었으나 시간초과

- 투포인터 학습 후 접근

- start와 end 설정이 중요하다.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

start = 1
end = max(arr)

while start <= end:
    mid = (start + end) // 2
    sumV = 0
    for i in arr:
        if i > mid:   # 높이보다 큰 나무 벌목
            sumV += i - mid
    if sumV >= M:       # 자른 나무 양 확인
        start = mid + 1
    else:
        end = mid - 1
print(end)

 

아래는 처음 구현한 시간초과 코드

(테스트케이스는 맞았으나 나머지는 모른다)

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse=True)

flag = 0
index = 0
line = 0
for i in range(1, N):
    sumV = 0
    if flag == 1:
        break
    for j in range(i-1):
        sumV += abs(arr[j]-arr[i])
    if sumV >= M:
        flag = 1
        index = i
        line = arr[i]
        break


switch = 1
while switch:
    sumV = 0
    for i in range(index):
        sumV += abs(arr[i] - line)
    if sumV >= M:
        result = line
        line += 1
    else:
        print(result)
        switch = 0