GitHub

https://github.com/Choidongjun0830

파이썬 알고리즘 문제 풀이

Baekjoon Online Judge 2805번 파이썬

gogi masidda 2022. 9. 19. 17:50

문제 링크
https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net


이 문제는 1654번 문제와 유사하다.
다른 점은 나무를 자르는 것이므로 나무의 높이가 자르는 높이보다 커야한다는 점이다. 그래서 ‘if t >= mid:’ 를 추가해주어야 한다.

정답 코드

import sys

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

start = 1
end = max(trees)

while start <= end:
  mid = (start + end) // 2
  result = 0
  for t in trees:
    if t >= mid:
      result += t - mid
  if result >= M:
    start = mid + 1
  else:
    end = mid - 1

print(end)
728x90