백준(BOJ) 24041 성싶당 밀키트(Python)

문제 내용.

 

이분 탐색 문제.

현재 날짜에 따라 세균수를 체크해야 하는데, 날짜는 최대 2e9까지 가능하므로 O(logn)으로 값을 탐색해야 할 것이라고 판단했고, "특정 조건을 만족하는 범위 내의 최댓값"을 구해야 하므로 이분 탐색을 사용해야함이 자명하다고 생각했다.

이때 각 날짜에 맞는 세균수를 구해야 하는데, 가장 먼저 k개의 중요하지 않은 재료를 빼야했다.

그리디하게 생각해보면 당연히 k번의 횟수를 모두 소모해야하는데, 중요하지 않은 재료가 k개 이상인 경우에는 현재 날짜를 기준으로 가장 세균수가 큰 재료들부터 빼줘야한다. 따라서 이분 탐색을 한 번 진행할 때마다 중요하지 않은 재료들을 현재 세균수를 기준으로 내림차순 정렬한 뒤, 그 중 순서대로 k개를 제외한 나머지 재료들의 세균수를 모두 더했다.

그 후에는 반드시 들어가야하는 재료들의 세균수를 더해 값을 체크하고 이분 탐색을 진행하거나 빠져나오는 방식으로 문제를 해결했다.

유통기한이 1e9이고 부패 속도가 1인 필수 재료만 존재하는 경우 날짜가 2e9로 최대이므로 end값은 2e9이다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

n,g,k=map(int,input().split())
L1=[]
L2=[]
start=0
end=int(2e9)
ans=0
for _ in range(n):
    s,l,o=map(int,input().split())
    if o:
        L1.append([s,l])
    else:
        L2.append([s,l])


while start<=end:
    mid=(start+end)//2
    vac=0
    if len(L1)>k:
        L1.sort(key=lambda x:(-x[0]*max(1,mid-x[1])))
        for i in range(k,len(L1)):
            vac+=L1[i][0]*max(1,mid-L1[i][1])
    for i in range(len(L2)):
        vac+=L2[i][0]*max(1,mid-L2[i][1])
    if vac<=g:
        ans=max(ans,mid)
        start=mid+1
    else:
        end=mid-1
print(ans)

경계값이 2e9임을 파악하는 것이 까다로웠다.