[BOJ 24395] 백준 24395번 - 명진이의 신년계획

		2022 중앙대학교 CHAC 풀이
A		[BOJ 24389] 2의 보수
B		[BOJ 24393] 조커 찾기
C		[BOJ 24392] 영재의 징검다리
D		[BOJ 24390] 또 전자레인지야?
E		[BOJ 24395] 명진이의 신년계획

1. 문제

$24395$. 명진이의 신년계획 (2022 중앙대학교 CHAC Open Contest E번)

백준 24395번 - 명진이의 신년계획 (https://www.acmicpc.net/problem/24395)

2. 풀이

여러 종류의 질병 중, 특정 개수의 질병들의 $R$과 $B$의 합으로 주어진 $(R, B)$를 만들 수 있는지 확인하고, 만들 수 있다면 이를 통해 만들어지는 위험군의 최소값을 구하는 작업을 구현해야 한다.

이는 weight와 value를 가진 조합 최적화 문제인 knapsack 개념과 비슷하다. 단지, weight 종류가 두 가지로 늘어났을 뿐이다.

knapsack 풀이 방식으로 문제를 해결한다고 하자. $M(M\leq 100)$가지 종류의 질병에 대해서 각각 $(R, B)$ 이차원 공간을 전부 탐색해야 한다. $M$의 최댓값은 $100$, $R$과 $B$의 최댓값은 $50$이다.

1. 공간 복잡도 $\rightarrow$ $R$이나 $B$의 총합의 최댓값은 $50*100=5000$이다. 따라서 $(R, B)$ 이차원 공간은 $5000\times 5000\times 4byte=100MB$의 공간이 필요하다. 이는 문제의 조건을 만족한다.

2. 시간 복잡도 $\rightarrow$ $100 \times (5000 \times 5000) = 25$억이다. $1$초에 $10$억번 연산을 기준으로 계산하면 $2.5$초가 나와서 문제의 시간 제한을 초과해버린다.

단순 구현으로는 문제의 시간 제한을 초과하기 때문에, 효율적으로 만들기 위한 약간의 사전 작업이 필요하다.

각각의 종류의 질병에 대해서 $5000 \times 5000$을 전부 탐색할 필요는 없다. 지금까지 나온 질병들의 $R$과 $B$의 총합을 넘길 수 없기 때문에, 그 범위까지만 탐색하면 된다.

따라서 Rsum, Bsum 변수를 만들어 누적합을 계산하며 그 범위까지만 탐색한다. 이때, $r$ 또는 $b$가 작은 순서대로 정렬한 다음 탐색해야 누적합(탐색 공간)을 최대한 늦게 증가시킬 수 있다.

밑의 ‘회고’에 좀 더 최적화된 풀이를 써놓았다.

3. 채점 결과

4. 회고

처음에 공간을 배열로 만들지 않고 map으로 구현하여서 map 탐색 과정에서 많은 시간을 소모하여 TLE를 받았다. 그렇게 두 번 TLE를 받고 자료구조를 배열로 고쳤고, 나중에는 $r$ 또는 $b$가 작은 순서대로 정렬하는 과정을 구현하지 않아서 TLE를 받았다.

이렇게 구현을 끝마쳤으나, 나중에 채점 현황을 둘러보니 공간복잡도와 시간복잡도가 훨씬 효율적인 코드들이 많아서 의문을 느끼고 분석해보았다. 그 결과, 각 질병에 대해서 $5000 \times 5000$ 탐색을 한 것이 아니라 $50 \times 50$ 탐색을 했다는 점을 발견하게 되었고 이유를 찾아보았다.

그 결과, $N$명의 학생의 input인 $R$과 $B$의 최댓값이 $50$이기 때문에 그렇다는 것을 알게 되었다. 입력의 최대값이 $(50, 50)$이므로 이 이상의 값을 계산할 필요가 없다는 것이었다. 이 점을 놓쳤기 때문에 벌어진 일이었다.

따라서 그냥 앞서 했던 정렬 사전작업을 할 필요도 없이 각 $M$개의 질병마다 $50 \times 50$ 탐색을 해주기만 하면, 시간제한 공간제한에 문제없이 효율적으로 동작한다. 아래 코드는 위 사항을 적용하여 최적화한 코드이다.

5. 코드