問題
http://community.topcoder.com/stat?c=problem_statement&pm=11096&rd=14514
下1桁が4または7である数はラッキーナンバーとなる。
ある整数Nが与えられたとき、その数をラッキーナンバーの和で表したい。
ラッキーナンバーの数で表すことができれば必要な最小のラッキーナンバーの
数を返す。
表すことができなければー1を返す。
解き方
チャレンジされやすそうな問題。
小さい数で試してみると、21以上の数はすべてラッキーナンバーの和で
表すことができることがわかる。
またラッキーナンバーの和で表すことができる場合、下2桁以外の数は
いくらであっても必要な数は変わらない。
よって作ることのできるすべての下3桁の数について試し、
その最小のものが答えになる。
単純に下2桁をMOD100でとると1020のような場合にー1となってしまうので
2桁の数で下1桁が4と7の数を引いたときの下2桁を求めれば
すべての場合で確かめることができる。
条件分岐のIF文をできるだけ少なくすることがシステムテストで落ちないためのコツ。
コード
class TheNumbersWithLuckyLastDigit {
public: int find(int n) {
int dp[100];
FORE(i,0,100)dp[i]=1e+9;
FORE(i,1,100){
if(i%10==4||i%10==7)dp[i]=1;
for(int j=4;i+j<100;j+=10)dp[i+j]=min(dp[i+j],dp[i]+1);
for(int j=7;i+j<100;j+=10)dp[i+j]=min(dp[i+j],dp[i]+1);
}
int ret=1e+9;
ret=min(ret,dp[n%100]);
for(int i=4;i<100&&n-i>=0;i+=10)ret=min(ret,dp[(n-i)%100]+1);
for(int i=7;i<100&&n-i>=0;i+=10)ret=min(ret,dp[(n-i)%100]+1);
return ret==1e+9 ? -1 : ret;
}
};
public: int find(int n) {
int dp[100];
FORE(i,0,100)dp[i]=1e+9;
FORE(i,1,100){
if(i%10==4||i%10==7)dp[i]=1;
for(int j=4;i+j<100;j+=10)dp[i+j]=min(dp[i+j],dp[i]+1);
for(int j=7;i+j<100;j+=10)dp[i+j]=min(dp[i+j],dp[i]+1);
}
int ret=1e+9;
ret=min(ret,dp[n%100]);
for(int i=4;i<100&&n-i>=0;i+=10)ret=min(ret,dp[(n-i)%100]+1);
for(int i=7;i<100&&n-i>=0;i+=10)ret=min(ret,dp[(n-i)%100]+1);
return ret==1e+9 ? -1 : ret;
}
};