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;
	}
};