[백준] 17503 맥주 축제 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/17503
• 🔑 이분 탐색
  • 맥주 종류를 선호도 기준으로 내림차순 정렬
  • mid값 (간 레벨)을 기준으로 정해진 개수만큼 맥주를 마시고 선호도를 채울 수 있는지를 확인
  • 만족한다면 mid값을 계속 낮춰보고 최솟값을 찾으면 끝 ✨

 

 

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
bear = [list(map(int, input().split())) for _ in range(k)]
bear.sort(reverse=True)

l = 0
r = 2**31

while l <= r:
    mid = (l+r) // 2        # 간 레벨

    sum_p = 0               # 먹은 맥주 선호도 합
    drink = 0               # 먹은 횟수
    for p, level in bear:   
        if mid >= level:    # 간 레벨 >= 도수
            sum_p += p
            drink += 1
        if drink == n:      # 먹을 만큼 먹었으면 그만 먹어
            break

    if sum_p >= m and drink == n:   # 선호도, 먹은 횟수 만족하면 값 줄여보기
        r = mid - 1
    else:
        l = mid + 1

if r != 2**31:
    print(l)
else:
    print(-1)