No.4 おもりと天秤

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 で間に合う

その他

  • これも動的計画法のお手頃問題として良い