https://www.acmicpc.net/problem/2805
sol) 사용한 알고리즘 : 이분탐색
💡문제이해
나무의 높이 : 20 15 10 17 , 최소 집으로 가져가려고 하는 나무의 길이 : 7
20-15 + 17-15 = 7 ⇒ 설정할 수 있는 최대 높이 : 15
🤔 이분탐색을 이용해 설정할 수 있는 최대 높이 찾기
1. 나무의 수 (n) , 집으로 가져오려고 하는 최소 나무의 길이 (m) 와 나무들의 길이(forest)
n , m = map(int,input().split())
forest = list(map(int,input().split()))
2. 처음 과 끝 point 설정
s = 0
e = max(forest)
3. 처음과 끝 점이 교차되지 않는 지점까지 가져갈 수 있는 나무의 길이를 계산
⇒ 만일 최소 나무길이에 만족한다면 처음 point를 mid+1로, 최소 나무길이보다 부족하다면 끝 point를 mid-1로 계산
while e >= s : #e와 s가 교차되지 않는 지점까지 반복
mid = (s+e) //2 #중간 포인트 설정
wood = 0
#가져갈 수 있는 나무 길이 계산
for tree in forest :
if tree >= mid :
wood += tree-mid
if wood >= m : #만일 최소 충족을 만족시킨다면
s = mid+1
else : #만일 최소 충족을 하지 못할 경우
e = mid -1
4. 최대 길이를 계산하므로 끝 point 출력
print(e)
5. 전체코드
n, m = map(int,input().split())
forest = list(map(int,input().split()))
s = 0
e = max(forest)
while e >= s :
mid = (s+e) // 2
wood = 0
for tree in forest :
if tree >= mid :
wood += tree-mid
if wood >= m :
s = mid +1
else :
e = mid -1
print(e)
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[백준] 1937번 욕심쟁이판다 - 파이썬 (0) | 2023.10.06 |
---|---|
[백준] 10815번 숫자카드 - 파이썬 (0) | 2023.10.06 |
[백준] 2606번 바이러스 - 파이썬 (2) | 2023.10.05 |
다이나믹 프로그래밍 - 파이썬 (1) | 2023.10.05 |
[백준] 14501번 퇴사 - 파이썬 (0) | 2023.10.04 |