S2 2805. 나무 자르기

문제 보기 :  2805번: 나무 자르기

---

문제

• 정답률 : 26%

---

작성 코드

n,m = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort(reverse=True)

low,high = 0,arr[0]
answer = 0

while low<=high:
    mid = (low+high)//2
    wood = sum(h-mid for h in arr if h>mid)

    if wood >= m:
        answer = mid 
        low = mid + 1
    else:
        high = mid - 1

print(answer)

---

풀이

와 진짜 오래 걸린 문제다....

이분 탐색에 자신이 없어서 (아직 알고리즘 파악이 덜 됐다) 선호하는 방식으로 풀이했는데 틀렸습니다 + 시간초과 콤보에 정신 나갈 것 같아서 이분 탐색으로 시야를 돌렸다... 흑흑

low를 arr[-1]으로 처음엔 두었는데 그렇게 하면 에러가 났고, 0으로 설정해야 딱 최대값과의 mid 값부터 탐색을 시작하게 되어 정답을 찾을 수 있었다.

while문은 low와 high를 활용한 mid를 '자르는 길이'로 두어 통나무의 길이 합을 확인하게 코드를 짰다.

이분 탐색 문제라 재풀이 해볼 예정이다...

선호하는 방식으로 풀이한 코드는 아래와 같다.

n,m = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort(reverse=True)
arr.append(0)
copy_m = 0

ar = [0] * (n+1)
for i in range(len(arr)-1):
    ar[i]=arr[i]-arr[i+1]
    copy_m += (ar[i])*(i+1)
    if copy_m >= m:
        break
if copy_m == m:
    print(arr[i+1])
elif copy_m > m:
    for length in range(arr[i],arr[i+1],-1):
        ls = 0
        for i in arr:
            if i>length: 
                ls += (i-length)
        if ls >= m:
            break
    print(length)