[BOJ/Python] 2805. 나무 자르기

📌 문제

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

2805번: 나무 자르기

 

📌 문제 접근 방법

알고리즘 분류가 이분 탐색이고, 대부분 이분탐색으로 풀이를 했던데 난 조금 다르게 접근해서 풀어보았다!

1. 처음엔 문제의 스토리텔링 순서대로 읽어가며 맨 위에서부터 차근차근 높이를 하나씩 낮추면서 탐색을 했다.
   

   

   
   
   • 결과는 시간 초과!
2. 그 다음엔 주어진 나무의 길이를 모두 더하고 필요한 만큼의 나무 길이를 빼준 후, 
   나머지만큼의 나무를 N개의 나무에 다시 나누어주는(?) 방식으로 풀이했다.
   • 만약 위의 예시처럼 주어졌다면 총 나무의 길이는 62이고 필요한 나무 길이는 7이다.
   • 그럼 먼저 총 길이(62)에서 필요한 나무 길이(7)를 확보해준다. (62 - 7 = 55, 55만큼의 나무가 남는다.)
   • 이를 다시 4개의 나무에 나누어 주기 위해 똑같이 분배하면 55/4 = 13 ··· 3 이 되는데,
     이 때 세 번째 나무의 원래 길이는 10이기 때문에 13을 분배할 수 없다.
   • 그러면 세 번째 나무를 제외하고 다시 나무를 나누어 준다.
     • 남은 나무의 총 길이는 55 - 10 = 45
     • 나누어 줘야할 나무의 개수는 4 -1 = 3
     • 45/3 = 15
   • 15는 남은 나무들(15, 17, 20)에게 분배가능하므로 15가 최대 높이가 된다!

 

뭔가 정석의 방식은 아니라서 나도 말로 설명하기가 어렵지만, 이렇게 안적어놓으면 분명 나중에 코드만 보고 이해할 수 없을 것 같아서 남겨놓는 기록...이랄까...ㅎ...

 

📌 코드

import sys

N, M = map(int, sys.stdin.readline().split())
trees = list(map(int, sys.stdin.readline().split()))

total = sum(trees)-M
trees.sort()

i = 0
while True:
    if trees[i] < total//N:
        total -= trees[i]
        N -= 1
    else:
        break

    i += 1

print(total//N)