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

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

 

# 성싶당 밀키트
import sys
from collections import defaultdict
input = sys.stdin.readline
N, G, K = map(int, input().split())
info = defaultdict(list)
for _ in range(N):
    speed, limit, isImportant = map(int, input().split())
    info[isImportant].append((speed, limit))


def get_g(x, k):
    result = 0
    for speed, limit in info[0]:
        result += speed*max(1, x-limit)
    info[1].sort(key=lambda k: -k[0]*max(1, x-k[1]))
    for t in range(k, len(info[1])):
        speed, limit = info[1][t]
        result += speed*max(1, x-limit)
    return result


result = 0
left, right = 0, int(2e9)
while left <= right:
    mid = (left+right)//2
    g = get_g(mid, K)
    if g <= G:
        result = mid
        left = mid + 1
    else:
        right = mid - 1
print(result)

 

이분탐색, 그리디
1. 입력을 받으면서 info 딕셔너리에 중요도가 0인 것과 1인 것의 재료들을 따로 받는다.
2. 이분탐색
    - left, right = 0, int(2e9) (최악의 경우 1e9*1e9)
    - get_g : 해당 날짜와 K개의 재료를 뺀 최소 세균 수
        - 0인 재료는 무조건 포함
        - 1인 재료는 세균수로 정렬을 해서 세균 수가 가장 큰 재료 K개를 뺀 나머지 포함 (그리디)
    - 가능한 세균수(G) 이하이면 result = mid, left = mid+1
    - 아니면, right = mid-1
3. result 출력

 

Good Bye, BOJ 2021! 문제에 출시된 나름 따끈따끈한 최신 문제이다.

최대 K개의 재료를 뺀다고 나와있는데 그리디로 접근해서

처음부터 K개의 재료를 제거하면 항상 최소 세균수가 나오게 된다. (이분탐색 밖에서 for문 X)

 

딕셔너리로 뺄 수 없는 재료와 뺄 수 있는 재료를 구분해서 넣었는데

그냥 리스트 두 개를 정의해도 충분하다.

 

세균 수는 각 N의 S * max(1, x - L) 합 <= G 이다. 문제 조건을 살펴보면 각 값의 최대 최소가 있다.
따라서 최악의 경우는 (N : 1, G : 1e9, S : 1, L : 1e9)를 대입한 값이 G 이하인 x는 2e9
S * max(1, x - L) <= G
1 * (x - 1e9) <= 1e9
x - 1e9 <= 1e9
x <= 2e9