ural 1073. Square Country

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 #define maxn 70000
 6 using namespace std;
 7 const int inf=99999999;
 8 int dp[maxn];
 9 int main()
10 {
11     int n;
12     scanf("%d",&n);
13     for(int i=1; i<=n; i++)
14     {
15         dp[i]=inf;
16     }
17     dp[1]=1;
18     for(int i=2; i<=n; i++)
19     {
20         int k=(int)sqrt((double)i);
21         for(int j=0; j<=k; j++)
22         {
23             dp[i]=min(dp[i],dp[i-j*j]+1);
24         }
25     }
26     printf("%d\n",dp[n]);
27     return 0;
28 }