[BOJ 24041] 백준 24041번 - 성싶당 밀키트

		Good Bye, BOJ 2021! 풀이
A		[BOJ 24039] 2021은 무엇이 특별할까?
B		[BOJ 24040] 예쁜 케이크
C		[BOJ 24041] 성싶당 밀키트
D		[BOJ 24042] 횡단보도

1. 문제

$24041$. 성싶당 밀키트 (Good Bye, BOJ 2021! C번)

백준 24041번 - 성싶당 밀키트 (https://www.acmicpc.net/problem/24041)

2. 풀이

최대 $K$개의 재료를 빼고 $x$일까지의 세균이 $G$마리 이하가 되게 만드는 최대 $x$를 찾는 문제이다.

$K$개를 빼는 건 제외하고 보았을 때, 임의의 $x$를 설정했을 때 총 세균 수를 계산 가능한데, $x$값이 클수록 세균 수가 많아지고 $x$값이 작을수록 세균 수가 줄어든다. 게다가 값의 범위도 넓으므로 Binary Search(이분 탐색)을 생각해볼 수 있다.

일 수를 기준으로 어떤 특정 일(mid)로 계산한 세균 수가 $G$보다 작거나 같으면 일 수를 늘려보고(left = mid+1), 세균 수가 $G$보다 크면 일 수를 줄여보는(right = mid-1) 방식으로 left, right를 좁혀 나가면 된다.

---

이제 $K$개의 재료를 빼는 것을 생각해보자. 세균 수의 총합이 $G$마리 이하가 되는 최대 $x$를 구해야 하므로, 특정 $x$가 정해져 있을 때 세균 수의 총합을 최대한 작게 만들어야 한다.

따라서, 특정 일(mid)이 정해져 있을 때(이분탐색 과정 내부에서), 각각의 재료에 대해서 생기는 세균 수 중 가장 큰 값을 최대 $K$개 빼서 세균 수의 총합을 구해서 이를 $G$와 비교하면 된다.

이때, $O(i)$가 $1$인 재료가 $K$개 미만일 수 있으니 총 $min(K, (O(i)=1$인 재료의 개수$))$만큼 재료를 빼야 한다.

---

유통기한이 적고, 만약 유통기한이 동일하다면 부패 속도 값이 큰 재료에 우선수위를 두는 방식으로 재료들을 정렬한 후, 그렇게 정렬된 재료들 중 최대 $K$개를 미리 빼고 나서 이분탐색을 실행하는 방식으로 구현하면 최적의 정답을 구할 수 없다.

유통기한이 적고 부패 속도 값이 큰 재료를 세균 수가 더 많이 나오는 재료라고 판단하는 것은 ‘$x$일’이라는 변수를 무시한 것이기 때문에 적절하지 않다. ($x$값이 무엇인지에 따라서 재료들의 세균 수의 순위가 변화한다.)

이 때문에 $x$값을 고정시킨 상태에서 각각의 세균 수를 비교해야 한다. 즉, 이분탐색을 하기 전에 정렬을 하는 것이 아니라, 이분탐색을 돌리면서($x$값을 고정시켜 놓고) 정렬을 해야 한다.

---

간단한 예시를 들어보자. $S=10,\, L=2$인 재료1과 $S=20,\, L=4$인 재료2가 있다.

	재료1의 세균 수	비교	재료2의 세균 수
2일	10	<	20
3일	10	<	20
4일	20	=	20
5일	30	>	20
6일	40	=	40
7일	50	<	60

이렇게 $x$(일 수)의 값에 따라서 우선순위가 계속 변하기 때문에 $x$를 고정시킨 후에 정렬을 해야 한다.

3. 채점 결과

4. 회고

.

5. 코드