[백준] 24041번 성싶당 밀키트 (파이썬)

문제해결 아이디어

• 이분탐색으로 mid는 몇일 지났는지 기준이 되는 날짜로 지정
• mid에 맞게 세균수를 기준으로 내림차순 정렬

소스코드

import sys
input = sys.stdin.readline

N,G,K = map(int,input().split())
# N개의 재료, G개의 세균수의 합 제한, K개까지 재료 뺄수있음

ing = []
for _ in range(N):
    ing.append(list(map(int, input().split())))
    # 부패속도, 유통기한, 재료 빼는 유무

s,e = 0, int(2e9)
ans = 0

while s <= e:
    mid = (s+e)//2
    k = 0
    g = 0
    ing.sort(key=lambda x:(-x[0]*max(1, mid-x[1]))) #세균수 내림차순

    for a,b,c in ing:
        if c == 1 and k < K: # 재료를 뺄 수 있을 떄 까지
            k += 1
        else:
            g += a*max(1, mid-b)        

    if g > G:
        e = mid-1
    else:
        ans = mid
        s = mid+1

print(ans)