SRM504.5 Div1 Easy - TheNumbersWithLuckyLastDigit

問題

足し合わせてnを作るために最小で何個の末尾4/7の数字が必要か求める

解法

4, 4*2, 4*3, 4*4、それらに7を足したもの、7, 4*5 で全ての1の位をカバーできる
これらに10kを足したものは構成要素のどれかに10kを足せば要素数を増やさずに作れる
ex) 19 = 4 + 4 + 4 + 7, 39 = 24 + 4 + 4 + 7
つまりn%10から答えが定まる
ただし位ごとに最小値があってそれより小さい値は作れないからチェックが必要
(例えばn%10=9では19が最小で9は作れない)

実装

作れる最小値と答えを手打ち

class TheNumbersWithLuckyLastDigit {
	public:
	int find(int n) {
		int mn[] = {20,11,12,23,4,15,16,7,8,19}, res[] = {5,2,3,5,1,3,4,1,2,4};
		return (n<mn[n%10] ? -1 : res[n%10]);
	}
};