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

2019. 3. 8. 13:16프로그래밍(주력)/백준 문제풀이

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


1300번

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
= int(input())
= 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)
 
cs

2805번

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
c, r = map(int, input().split(' '))
= 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)
cs