BOJ 15759 - Talent Show

May 21, 2023

Knapsack DP인건 어렵지 않게 알 수 있고, 유리수를 다뤄야 한다는 점이 까다롭다.

또한, $W$ 에도 제한이 걸려 있어서 $O(NW)$ 로 DP를 돌릴 때, $W$ 를 넘어가는 시점이 있다면 따로 최대값을 업데이트만 해주고 DP 테이블을 건들지 않는 방식으로 처리해줘야 한다.

$\dfrac{t_i}{w_i}$ 를 기준으로 내림차순 정렬을 한 다음에 DP를 돌려야 한다.

이게 왜그런지 모르겠다.

정해Permalink

이분탐색을 사용한다.

현재 $x$ 가 가능한지에 대해 판단하고 있고 골라진 소들의 집합이 $S$ 라고 할 때,

$\dfrac{\sum_{i \in S} t_i}{\sum_{i \in S}^{} w_i} \ge x,\ \ \sum_{i \in S}^{} w_i \ge W$ 여야 한다.

\begin{align} \dfrac{\sum_{i \in S} t_i}{\sum_{i \in S}^{} w_i} \ge x \\ \sum_{i \in S} (t_i-xw_i) \ge 0 \end{align}

으로 표현될 수 있고, $v_i=t_i- xw_i$ 로 따졌을 때

$v_i$ 들의 값의 합이 $0$ 이 되는 조합이 있고 그 때 무게의 합이 $W$ 이상이라면 $x$ 가 가능한 것이므로 이를 knapsack 으로 판별해줄 수 있다.

따라서 $O(wn)$ 이 걸리고 이분탐색까지 $O(wn \log t)$ 가 걸린다.