[Python/파이썬] 백준 14575번 뒤풀이

14575번: 뒤풀이

 

코드

n, t = map(int, input().split())
alcohol = [list(map(int, input().split())) for _ in range(n)]

s, e = 1, int(1e9)
ans = int(1e9)
while s <= e:
    mid = (s+e)//2
    # 나눠주는 술의 총량 계산
    low, high = 0, 0
    for i in range(n):
        if alcohol[i][0] > mid:
            low = -1
            break
        low += alcohol[i][0]
        high += min(mid, alcohol[i][1])
    if low == -1 or high < t:
        s = mid+1
    else:
        if low <= t <= high:
            ans = min(ans, mid)
        e = mid-1
print(ans if ans != int(1e9) else -1)

 

매개 변수 탐색을 이용하여 가능한 S 중 최소값을 찾을 것이다.

매개 변수 탐색을 하기 위해서는 범위에서 절반으로 나눈 왼쪽으로 갈지 오른쪽으로 갈지 정하는 조건이 필요하다. 그 조건은 현재 mid가 최대로 줄 수 있는 술의 양, 즉 S라고 할 때 모든 사람에게 줄 수 있는 술의 최소값과 최대값을 이용하여야 한다. 이 최소값을 low, 최대값을 high라 하자.

• ①어느 한 사람의 주량 최소치보다도 작거나 ②최대치인 high가 T보다 작을 때, S를 더 크게 만들어줘서 모든 사람의 주량 최소치보다 S가 크고, high가 T보다 크게 만들어야 한다.
• 그 반대일 때는 만약 low <= T <= high라면 우리가 원하는 양만큼 줄 수 있는 경우이므로 ans = min(ans, mid) 그리고 나서 더 작은 S가 존재하는지 알아보기 위하여 나눈 범위 왼쪽으로 간다.