SRM544 Div2 Medium - BoardSplitting
問題
長さkの板が無限にある
これらを切ったりくっつけたりして長さLの板をn枚作りたい
長さkの板を必要最小限の枚数だけ使うとき、最低何回板を切る必要があるか求めよ
1 <= n, m, k <= 1000
解法
貪欲
長さkの板を切って余った板を寄せ集めてちょうど長さLにできる場合はコストがかからない
できない場合は余りと合わせると長さLになるような長さの板を新しく作るしかない
class BoardSplitting { public: int minimumCuts(int l, int n, int k) { int res = 0, rem = 0; while (n--) { while (rem<l) rem += k; rem -= l; if (rem) res++; } return res; } };