[백준 14575번] 파이썬 - 뒤풀이

백준 14575 - 뒤풀이

시간 제한 1초, 메모리 제한 128MB

# 조건

• 도현이는 이번 대회를 준비하면서 거한 저녁 만찬을 예약했다.
• 하지만 모종의 이유로 요리사들이 모두 천국으로 떠나버렸기 때문에, 도현이는 어쩔 수 없이 평범한 신촌 술집을 뒤풀이 장소로 정할 수밖에 없었다.
• 도현이는 우선 각 사람에게 어느 정도 마시면 기분이 좋은지(Li)와, 어느 정도 마시면 힘든지(Ri)를 물어보았다.
• 각 사람은 Li미만의 술을 마시면 술이 부족해 기분이 좋지 않고, Ri를 초과하는 술을 마시면 천국으로 가버릴 수도 있다.
  • 도현이는 각 사람들에게 적당량씩 술을 분배하려고 한다.
• 그런데 신촌 술집이 항상 그렇듯이, 사장님은 도현이에게 T이상의 술을 반드시 팔아줘야만 예약을 잡아주겠다고 엄포를 놓았다.
• 마침 도현이의 통장엔 정확히 T의 술을 살 수 있는 금액이 들어 있었고, 도현이는 정확히 T의 술을 결제하였다.
• 이제 도현이는 모든 사람 i에게 Li이상 Ri이하의 술을 주면서, 그 총합이 정확히 T가 되도록 술을 분배하려고 한다.
• 하지만 안타깝게도, 사람들은 자신의 주량을 과대평가하는 경향이 있다.
• 이에 따라 도현이는 S의 값을 정하고, 각 사람에게 그 사람이 원하는 술의 양이 얼마이던지 관계없이 S이하의 술만을 주려고 한다.
• 이제 도현이는 술도 결제했고, 주량도 조사했으므로,
  1. 모든 사람 i가 Li이상 Ri이하의 술을 받으면서,
  2. 모든 사람이 받은 술의 총합이 정확히 T가 되고,
  3. 어떤 사람도 S를 초과하는 술은 받지 않게 할 수 있는,
• 그러한 S값만 결정하면 된다.
• 도현이를 도와 조건을 만족하는 S값을 찾아주도록 하자.
  • 만약 그런 값이 여러 개라면, 도현이는 그 중 가장 작은 값을 찾고 싶다.

입력

• 첫째 줄에 대회 참가자의 수 N과 술의 총량 T가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ T ≤ 10^9)
• 둘째 줄부터 N개의 줄에 걸쳐, 각 사람에 대한 Li와 Ri값이 주어진다. (1 ≤ Li ≤ Ri ≤ 10^6)

출력

• 만약 S의 값과는 관계없이 항상 불가능하다면 첫째 줄에 -1만을 출력한다.
• 문제의 조건을 만족하는 S값이 존재한다면 가장 작은 값 하나를 출력한다.

# 접근 방법

• 우선, 모든 사람들이 최대 주량으로 마셨을 때 T보다 작거나 최소 주량으로 마셨을 때 T보다 크다면 T를 정확히 맞출 수 없으므로 -1을 출력해준다.
• 위의 조건을 통과했다면 이분 탐색을 이용하여 풀어준다.
• 탐색을 시작하며 자신의 주량안에서 S를 초과하지 않고 T를 정확히 맞추기 위해선 아래와 같은 로직을 수행해준다.
  • 모든 사람을 최소의 주량으로 먹인다.
  • 이 때, 최소의 주량으로 먹이며 최대 - 최소의 값과 S-최소의 값 중 작은 값을 can_more 변수에 더해가며 저장해준다.
  • 마지막에 마셔야되는 남은 양 <= can_more이라면 정확히 T만큼 먹일 수 있음을 알 수 있다.
• 예를 들면 3 5, 4 8의 주량을 가진 사람이 있고 s가 5, T = 11이라고 가정해보자
  • 최소의 주량으로 먹인다면 T는 4만큼 더먹어야 하고
  • 1번의 사람은 2, 2번의 사람은 1만큼 더 먹을 수 있기 때문에 can_more는 3이 될 것이다.
  • 즉, 더 먹어야 하는 4의 양은 1번과 2번 사람에게 배분하여 충족시킬 수 없는 것을 확인할 수 있다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, T = map(int, input().split())  
people = []  

# 최소 주량과 최대 주량 더해주기  
# 이 값이 T보다 크거나 작으면 T를 맞출 수 없으므로  

min_value = 0  
max_value = 0  
left = -1  
right = -1  
for _ in range(N):  
    a, b = map(int, input().split())  
    people.append([a, b])  
    min_value += a  
    max_value += b  
    if left < a:  
        left = a  
    if right < b:  
        right = b  

if min_value > T or max_value < T:  
    print(-1)  
    exit()  

result = float('inf')  

# 이분 탐색 이용  
while left <= right:  
    mid = (left + right) // 2  
    total = T  
    can_more = 0  
    # 모든 사람 순회하면서 설정된 s값 이하로 마시면서 자기의 주량에 맞게 마시는 지 체크  
    # 이 때, 최소 주량 + 남는 주량이 T보다 크면 된다.    
    for i, j in people:  
        total -= i  
        # 최소 주량만큼 전부 마시면서 남는 나의 주량 저장  
        # ex) 2 5이고 mid가 4라면 2만큼 마시고 2만큼 더 마실 수 있다.        # s에서 최소 주량 뺀 값과, 최대 주량에서 최소 주량을 뺀 값 중 작은걸로 저장해주어야 함        
        can_more += min(mid - i, j - i)  

    if can_more >= total:  
        if result > mid:  
            result = mid  
        right = mid - 1  
    else:  
        left = mid + 1  

print(result if result != float('inf') else -1)