BOJ 9327 - 용량 확보
$S_i$가 작음을 본다. $\sum S_i \le 2 \cdot 10^5$ 이기 때문에 DP를 쓸 수 있다.
$dp[i]$ 를 용량 $i$ 를 절약할 수 있는지 여부라고 하면 $O(n \cdot \sum S_i)$ 정도로 이걸 체크할 수 있고, $e$ 이상인 것 중 가능한 것중 가장 작은 값이 정답이다.
bitset을 이용하면 더 빠르게 DP를 돌릴 수 있다.
$S_i$가 작음을 본다. $\sum S_i \le 2 \cdot 10^5$ 이기 때문에 DP를 쓸 수 있다.
$dp[i]$ 를 용량 $i$ 를 절약할 수 있는지 여부라고 하면 $O(n \cdot \sum S_i)$ 정도로 이걸 체크할 수 있고, $e$ 이상인 것 중 가능한 것중 가장 작은 값이 정답이다.
bitset을 이용하면 더 빠르게 DP를 돌릴 수 있다.
Comments