2019.03.08) 백준 이분탐색 특집 2편 -1300, 2805 (PyPy3)

이분탐색은 이상한데도. 쓰일수가 있구나를 알았다

1300번

c = int(input())
h = int(input())
 
left = 1
right = h
 
while right >= left:
    count = 0
    mid = (left + right) // 2
    # 최소 높이만큼 더하기
    for i in range(1, c + 1):
        count += min(mid // i, c)
    if count < h:
        left = mid + 1
    else:
        r = mid
        right = mid - 1
 
print(r)
 

2805번

c, r = map(int, input().split(' '))
l = list(map(int, input().split(' ')))
l.sort()
 
# 나무의 길이는 0부터
left = 0
# 최고로 큰 나무까지 가능하다
right = l[-1]
re = 0
while left <= right:
    mid = (left + right) // 2
    count = 0
    # 탐색하는 중간값을 기준으로 나무를 자르고 저장
    for i in l:
        if i > mid:
            count += i - mid
    if count == r:
        re = mid
        break
    elif count < r:
        right = mid - 1
    elif count > r:
        re = mid
        left = mid + 1
 
print(re)