백준24041(성싶당 밀키트) python - 참고 해결

성싶당 밀키트

 

문제

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

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

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

 Si×max(1,x−Li)\[ S_i \times \max\left( 1, x-L_i \right) \] 

마리이다. 단, $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 \le N \le 200\,000$ 
•  $1 \le G \le 10^9$ 
•  $0 \le K < N$ 
•  $1 \le S_i \le 10^9$ 
•  $1 \le L_i \le 10^9$ 
•  $O_i \in \left\{0,1\right\}$ 
• 모든 재료의 $S_i$의 합은 $G$를 넘지 않는다. ($\sum_{1 \le i \le n} S_i \le G$)
• 입력으로 주어지는 모든 수는 정수이다.

---

이분 탐색 문제였다.

이분 탐색은 항상 뭔가 헷갈린다.

처음과 끝, 언제 끝나야하는지 

https://www.acmicpc.net/blog/view/109

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

해당 사이트를 참고하였다.

하지만 진짜 매번 헷갈린다....

어떻게 하는지 제대로 판단해봐야겠다.

방법 자체는 각 음식의 세균수를 판단하고 제외할 수 있는 음식은 따로 저장해서 내림차순으로 정렬.

그리고 K 개를 제외하고 합한다.

그리고 이분 탐색.

그리고 틀린 이유가 하나있었는데 끝을 $10^9$로 해서 틀렸다. 최대 $2*10^9$였다...

 

import sys
input = sys.stdin.readline

N, G, K = map(int,input().split())

kits = [list(map(int,input().split())) for _ in range(N)]

def check(x):
    O_list = []
    cnt = 0
    for i in range(N):
        s = kits[i][0] * max(1,x-kits[i][1])
        if kits[i][2]:
            O_list.append(s)
        else:
            cnt += s
    
    O_list.sort(key=lambda x:-x)
    if len(O_list) > K:
        cnt += sum(O_list[K:])

    # print(cnt)
    if cnt > G:
        return 0
    else:
        return 1
    

l = 0
r = 2*(10**9) + 1

while l <= r:
    mid = (l+r)//2
    if check(mid):
        l = mid + 1
    else:
        r = mid - 1

print(r)