[백준 14575 🥈] 뒤풀이

https://www.acmicpc.net/problem/14575

14575번: 뒤풀이

문제

도현이는 이번 대회를 준비하면서 거한 저녁 만찬을 예약했다.

하지만 모종의 이유로 요리사들이 모두 천국으로 떠나버렸기 때문에, 도현이는 어쩔 수 없이 평범한 신촌 술집을 뒤풀이 장소로 정할 수밖에 없었다.

도현이는 우선 각 사람에게 어느 정도 마시면 기분이 좋은지(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 ≤ 109)

둘째 줄부터 N개의 줄에 걸쳐, 각 사람에 대한 Li와 Ri값이 주어진다. (1 ≤ Li ≤ Ri ≤ 106)

출력

만약 S의 값과는 관계없이 항상 불가능하다면 첫째 줄에 -1만을 출력한다.

문제의 조건을 만족하는 S값이 존재한다면 가장 작은 값 하나를 출력한다.

 

문제 풀이

import sys

n,t=map(int, sys.stdin.readline().strip().split(' '))

L=[]
R=[]
for _ in range(n):
    l,r=map(int, sys.stdin.readline().strip().split(' '))
    L.append(l)
    R.append(r)

# 최소 주량을 모두 더했는데 t보다 크다면 불가능한 경우
if sum(L)>t:
    print(-1)
    sys.exit(0)
# 최대 주량을 모두 더했는데 t보다 작다면 불가능한 경우
if sum(R)<t:
    print(-1)
    sys.exit(0)

def possible(mid):
    more=0
    min_adding=0
    for l,r in list(zip(L,R)):
        min_adding+=l
        if l<=mid<=r:
            more+=(mid-l)
        elif mid>r:
            more+=(r-l)
    if more>=(t-min_adding):
        return True
    else:
        return False

startS=max(L)
endS=max(R)
mid=(startS+endS)//2

while startS<=endS:
    mid = (startS + endS) // 2
    # S가 mid일 때 가능한가?
    if possible(mid):
        # 가능할 경우 -> mid 값을 더 줄일 수 없는지?
        endS=mid-1
    else:
        # 불가능할 경우 -> mid 값을 더 늘려도 불가능한가?
        startS=mid+1

print(mid)

• 사람들의 최소 주량(Li)을 모두 더해서 T보다 클 경우 불가능한 경우이므로 -1을 출력하고 프로그램을 종료한다.
• 사람들의 최대 주량(Ri)을 모두 더해서 T보다 작을 경우 불가능한 경우이므로 -1을 출력하고 프로그램을 종료한다.
• 위 경우를 모두 통과할 경우 이분탐색을 이용해서 적절한 S값을 찾는다.
  • S값이 어떤 사람의 최소 주량보다 작을 경우, 해당 사람의 주량 범위를 만족할 수 없기 때문에, S값은 최소 주량들 중 최댓값 이상이어야 한다.
  • S값이 최대 주량들의 최댓값보다 커지는 경우부터는 사람들의 주량 범위를 모두 만족하게 되므로 S 값이 더 커지더라도 결과는 똑같다. 
  • 그래서 S값 이분 탐색을 위한 startS와 endS를 각각 최소 주량들의 최댓값, 최대 주량들의 최댓값으로 두고 이분탐색을 구현했다.
  • 어떤 S 값이 모든 사람들의 범위를 만족하면서, 사람들이 마신 술의 총량이 T가 될 수 있는 경우인지는 다음과 같은 과정으로 확인한다.
    • 먼저 모든 사람들이 최소 주량만큼만 마셨다고 가정한다.
    • 그리고 각 사람별로 주량 범위와 S값을 고려해서 얼마나 더 마실 수 있는지 파악한다.
      • S값이 Li와 Ri 사이의 값이라면 S-Li만큼 더 마실 수 있고, S값이 Ri보다 크다면 Ri-Li만큼 더 마실 수 있다.
    • 이 파악한 값들은 변수 more에 저장해두고 more가 총량 T에서 최소 주량을 뺀 값보다 크다면 가능한 경우라고 판단한다.
    • 가능한 경우라면 endS=mid-1로 더 작은 S값이 가능한지 파악하고, 불가능하다면 startS=mid+1로 더 큰 S값으로는 가능한지 파악한다.
    • 이러한 과정을 반복하면서 가장 작은 S값을 찾는다.