[BOJ 24041 🥇4] 성싶당 밀키트 (Python)

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

24041번: 성싶당 밀키트

문제

인스타 빵타쿠들의 꾸준한 사랑을 받는 베이커리 <성싶당>은 수현이가 그동안 쌓아온 노하우를 바탕으로 밀키트 사업에도 진출했다! 이제 성싶당의 맛을 집에서도 즐길 수 있다!

이 소식을 놓칠 리 없는 빵타쿠 한별이는 바로 성싶당에 달려가 밀키트를 사 왔다. 그러나 문제를 푸느라 바쁜 한별이는 깜빡 잊고 유통기한 안에 밀키트를 먹지 못했다. 눈물을 머금고 밀키트를 버리려고 포장을 뜯은 순간 한별이는 재료마다 유통기한이 다르다는 것을 발견했다. 밀키트의 유통기한은 모든 재료의 유통기한 중 가장 이른 것으로 결정되기 때문에 아직 유통기한이 지나지 않은 재료들이 남아 있었다.

밀키트에는 N 개의 재료가 들어 있다. i 번째 재료의 유통기한은 밀키트를 구매한 후 L_i 일까지이고, 부패 속도는 S_i이다. 이 때 구매 후 x 일에 i 번째 재료에 있는 세균수는S_i * max( 1, x- L_i ) 마리이다. 단, x는 정수이다.

모든 재료의 세균수의 합이 G마리 이하일 경우 안심하고 먹을 수 있다. 밀키트를 너무 먹어보고 싶은 한별이는 중요하지 않은 재료를 최대 K 개까지 빼서 세균수가 G 마리 이하가 된다면 그냥 먹기로 했다.

한별이는 밀키트를 산 날부터 며칠 후까지 먹을 수 있을까?

 

입력

첫 번째 줄에 N, G, K가 공백으로 구분되어 주어진다.

두 번째 줄부터 N 개의 줄 중 i 번째 줄에는 i 번째 재료에 대한 정보인 부패 속도 S_i, 유통기한 L_i와 중요한 재료인지를 나타내는 수 O_i가 주어진다. O_i는 0 또는 1이며,O_i=1은 재료가 중요하지 않아서 뺄 수 있다는 의미이다.

 

출력

중요하지 않은 재료를 최대 K 개까지 뺐을 때, 밀키트를 구매 후 며칠 후까지 먹을 수 있는지 출력한다.

 

제한

•  1≤ N ≤200000
•  1≤ G ≤10^9 
•  0≤ K < N 
•  1≤ S_i ≤10^9 
• 1≤ L_i ≤10^9 
•  O_i∈{0,1}
• 모든 재료의 S_i의 합은 G를 넘지 않는다.
• 입력으로 주어지는 모든 수는 정수이다.

 

예제 입력 1 

4 36 0
2 14 1
3 8 1
5 12 1
7 10 0

 

예제 출력 1 

12

 

예제 입력 2 

4 36 1
2 14 1
3 8 1
5 12 1
7 10 0

 

예제 출력 2 

13

 

예제 입력 3 

4 36 2
2 14 1
3 8 1
5 12 1
7 10 0

 

예제 출력 3 

14

 

⭕ CODE

import sys

input = sys.stdin.readline

n, g, k = map(int, input().split())

arr = []

# 구매 후 x일에 i번째 재료에 있는 세균수
# s_i * max(1,x-l_i)

for _ in range(n):
    s, l, o = map(int, input().split())
    arr.append((s, l, o))

# 시작지점 1
# 끝지점을 문제의 조건을 보면
#  S * max(1, x - L) <= G 가 있다
# 여기에 N = 1, G = 1e9, S = 1, L = 1e9 를 대입하면
# x <= 2e9가 나온다.
# 처음에는 모든 재료에서 유통기한이 제일 긴 친구를 하면 되겠지 했는데
# 질문 게시판 읽어보니 아니더라
s = 1
e = int(2e9)

# 이분탐색 시작
while s <= e:

    # 세균 수
    virus = 0

    mid = (s + e) // 2

    # 재료를 뺄 회수 count
    count = 0

    # 각각의 요일마다 세균수가 최소인것을 기준으로 정렬해주기
    arr.sort(key=lambda x: (-x[0] * max(1, mid - x[1])))

    for i in range(n):
        # 중요하지 않은 재료이고
        # 뺀 재료의 수가 k개 보다 작다면
        # 재료를 빼주고 뺀 회수 + 1
        if arr[i][2] == 1 and count < k:
            count += 1
        # 그게 아니라면
        else:
            # 세균 수 증가
            virus += arr[i][0] * max(1, mid - arr[i][1])

    # 세균 수가 g마리 이하라면 먹을 수 있다.
    if virus <= g:
        # mid 보다 하루 더 먹어도 괜찮으므로
        # s = mid + 1
        s = mid + 1
    # 세균 수가 g마리 보다 많다면 먹을 수 없다
    else:
        # 지금 날짜보다 작아져야한다
        # 끝지점을 mid-1 해주기
        e = mid - 1

# 결과 출력
print(e)

✏️ Comment

처음에는 우선적으로 정렬을 하고 문제를 풀려고 했는데 날짜에 따라서 세균 수가 달라져서 내가 선택한 날짜(mid)에 대하여 세균수가 최소인것을 기준으로 정렬해주었다 arr.sort(key=lambda x: (-x[0] * max(1, mid - x[1])))

시작지점을 1로 잡고 끝지점을 문제의 조건을 보면 S * max(1, x - L) <= G 가 있다
여기에 N = 1, G = 1e9, S = 1, L = 1e9 를 대입하면
x <= 2e9가 나온다. 그러므로 끝지점을 2e9로 잡아준다.
처음에는 모든 재료에서 유통기한이 제일 긴 날짜를 끝지점으로 잡는다고 생각했는데 질문 게시판을 읽어보니 그러한 내용이 있어서 수정하였다. 시작과 끝지점을 초기 설정을 잘 해주는게 매우 중요하다고 느낀 문제였다.