[Algorithm] 이진탐색 - 2417.py 13702.py

2417.py

# https://www.acmicpc.net/problem/2417

n = int(input())

start = 0
end = n
while start <= end:
    mid = (start + end) // 2
    if mid ** 2 < n:
        start = mid + 1
    else:
        end = mid - 1

print(start)

a가 4일때 2는 4의 제곱근이라고 한다. 즉 a를 제곱해서 b가 나오면 a는 b의 제곱근이라고 한다.

제곱근을 구하는 방법인데 mid를 2로 나눈값을 두고 그 값을 제곱해서 n보다 크면 end값을 mid-1로 작으면 start값ㅇ,ㄹ mid+1로 바꾼다.
헷갈리는 부분은 부등호였다.
<=이렇게 했더니 정답이 계속 안나왔다...
이유는 start를 보여주는데 <=이렇게 되면 start값이 바뀌어서 인것같다.

13702.py

# https://www.acmicpc.net/problem/13702
n, k = map(int, input().split())

data = [int(input()) for _ in range(n)]

start = 0
end = max(data)
result = 0
while start <= end:
    num = 0
    mid = (start + end) // 2
    for i in data:
        a = i // mid
        num += a
    if num < k:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

몫을 가지고 구하는 문제이다.
남은 술은 버릴거기 때문에 mid는 가장 큰값에서 2로 나눈값으로 하고 각 술 용량을 mid로 나눠서 나누어줘야할 사람수 k와 몫을 비교해 구한다.

15732

https://www.acmicpc.net/problem/15732
못풀겟다!!

코드를 입력하세요