ones 게이지

정수 n을 주십시오. 값이 n인 표현식을 찾으십시오. 이 표현식은 1 + * ()만 충분합니다.그리고 1은 연속할 수 없다. 예를 들어 11+1은 비합법적이다.
n 을 입력하여 (1<=n<=10000)
출력은 최소한 몇 개의 1이 있어야만 표현식을 구성할 수 있다.
예: n=2=1+1 ans=2
       n=10=(1+1)*(1+1+1+1+1)   ans=7
 
[한 수의 i가 소수일 때 이 수는 i개의 1로만 구성될 수 있음을 알 수 있다. 그러나 그것이 소수가 아닐 때 이 수를 그 인자의 곱셈 형식으로 나눌 수 있다.]
dp[i]로 하여금 최소 수량의 1을 표시하여 i를 나타낼 수 있게 하다.
add:        dp[i]=dp[j]+dp[i-j]  0multiply: dp[i]=dp[j]+dp[i/j]0#include<iostream> #include<algorithm> #include<cstdio> using namespace std; int dp[10000]; void dps() { int i,j; dp[0]=0; dp[1]=1; for(i=2;i<10000;i++) { dp[i]=i; for(j=1;j<i;j++) { dp[i]=min(dp[i],dp[j]+dp[i-j]); if(i%j==0) dp[i] = min(dp[i],dp[j]+dp[i/j]); } } } int main() { int n; dps(); while(scanf("%d",&n)!=EOF) { printf("%d
",dp[n]); } return 0; }