🗂️ 문제
링크: https://www.acmicpc.net/problem/2805
💡 접근법
N과 M의 범위가 크기 때문에 모든 경우의 수를 계산할 경우 시간초과가 발생한다.
절단 높이를 작게하면 가져가는 나무의 길이가 크고, 절단 높이를 크게하면 가져가는 나무 길이기 작다.
이를 이용하여 절단 높이를 기준으로 이분 탐색을 수행한다.
또한 절단 높이를 최대로 하여 필요한 만큼의 나무를 가져가므로, 나무의 길이가 딱 떨어지지 않는 경우를 생각해야 한다. 이 경우엔 high(mid-1)
값을 출력하면 필요한 만큼 나무를 가져가면서 최대로 하는 절단 높이를 구할 수있다.
😎 내 코드
import sys
N, M = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))
def cal_tree(height):
sum = 0
for t in tree:
if t-height > 0:
sum += t - height
return sum
low = 0
high = max(tree)
while (low <= high):
mid = (low+high) // 2 # 절단 높이
tree_height = cal_tree(mid) # 가져가는 나무 길이
if tree_height == M:
print(mid)
break
else:
if tree_height < M:
high = mid - 1
elif tree_height > M:
low = mid + 1
if low > high: # 나무 길이기 딱 떨어지지 않는 경우
print(high)
✅ 정답 확인
'Algorithm > Baekjoon' 카테고리의 다른 글
[DP] 백준 #11726 2xn 타일링 - Python (0) | 2024.05.05 |
---|---|
[이분탐색] 백준 #1654 랜선 자르기 - Python (1) | 2024.05.03 |
[DP] 백준 #9095 1, 2, 3 더하기 - Python (0) | 2024.04.09 |
[DP] 백준 #2579 계단오르기 - Python (0) | 2024.04.06 |
[DP] 백준 #24416 알고리즘 수업 - 피보나치 수 1 - Python (0) | 2024.04.03 |