[파이썬] 백준 24041 : 성싶당 밀키트 (골드4)

[파이썬] 백준 24041 : 성싶당 밀키트 (골드4)

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

---

풀이

방향성 생각

• NlogN -> 정렬 or 힙?
• 세균 수를 결정하는 요소가 2가지
  • 날짜 역순으로 접근해서 풀이하기 어려움
  • 단일 변수면 특정 날짜에서 우선순위가 바로 정해지지만 2변수라 계산을 무조건 해야함
• 범위가 2*1e9까지 가능 -> 최대 31회의 탐색으로 최대값 찾기 가능
  • $31NlogN$으로 풀이가 가능
  • 시간을 줄이기 위해서 루프 탈출 조건을 넣어준다.

 

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

def calc(S,L,day):
    return S*max(1,day-L)

def eat(array,day,K):

    score = 0
    temp = []
    for S,L,O in array:

        if not O: # 필수는 바로 계산
            score += calc(S,L,day)
        else: # 필수 아니면 정보 저장
            temp.append(calc(S,L,day))

        # 중간에 세균 수 넘어가면 False
        if score > G:
            return False

    # 필수 아닌 재료 중 상위 K개 제거
    temp.sort(reverse=True)
    if score + sum(temp[K:]) > G:
        return False
    return True

N,G,K = map(int,input().split())
infos = [tuple(map(int,input().split())) for _ in range(N)]

l,r = 0,2*(10**9)
while l<=r:
    m = (l+r)//2
    if eat(infos,m,K):
        answer = m
        l = m+1
    else:
        r = m-1
print(answer)

코멘트

• 1이 필수고 0이 필수가 아닌줄...