Quiz
https://yukicoder.me/problems/no/4
Submit
https://yukicoder.me/submissions/330176
解法
- 天秤の両方を気にするのは大変
- 重さの合計 / 2 を片側で作れるかで判定すればいい
- 各重りを使う・使わないで分岐したらO(2100)となってしまう
- dp[i][j] : i番目まで見た時に重さ j を作ることができるか
- と定義する
- 表の大きさは、
- i <= 100
- j <= 10000
- この表を埋めるコストは100 x 10000 = 106 で間に合う
その他
- これも動的計画法のお手頃問題として良い