BOJ 15759 - Talent Show
Knapsack DP인건 어렵지 않게 알 수 있고, 유리수를 다뤄야 한다는 점이 까다롭다.
또한, $W$ 에도 제한이 걸려 있어서 $O(NW)$로 DP를 돌릴 때, $W$를 넘어가는 시점이 있다면 따로 최대값을 업데이트만 해주고 DP 테이블을 건들지 않는 방식으로 처리해줘야 한다.
$\dfrac{t_i}{w_i}$를 기준으로 내림차순 정렬을 한 다음에 DP를 돌려야 한다.
이게 왜그런지 모르겠다.
정해
이분탐색을 사용한다.
현재 $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)$ 가 걸린다.
Comments