[BOJ/C++]1699번 제곱수의 합

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

---

문제

 자연수 n을 $11=2^2+2^2+1^2+1^2+1^2$ 혹은 $11=3^2+1^2+1^2$와 같은 제곱수들의 합으로 나타낼 수 있다. 이때 표현할 수 있는 제곱수 항의 최소 개수를 구해라.

풀이

 i가 제곱수로 표현가능한 경우, 즉 i=j*j인 경우는 dp[i]가 1이다. 

그 경우 dp[i]에 1을 넣어주고, 그 외에 경우에는 일단 dp[i]=dp[i-1]+1을 해 준다(직전 경우에 $1^2$를 더한 경우의 수)

 

그리고 j가 1부터 $j^2$가 i보다 작을 때 까지 i를 늘려주며 dp[i-$j^2$]+$j^2$를 한 경우가 현재의 dp[i]값보다 작은지 비교하며 dp[i]값을 정한다.

 

소스코드

#include<iostream>
#include<cmath>
using namespace std;

int main(void){
    int n;
    cin>>n;
    int dp[n+1];

    dp[1]=1;
    for(int i=2;i<=n;i++){
        dp[i]=dp[i-1]+1;
        if(0==sqrt(i)-(int)sqrt(i)){
            dp[i]=1;
            continue;
        }
        for(int j=1;j*j<i;j++){
            dp[i]=min(dp[i],dp[i-j*j]+1);
        }
    }
    cout<<dp[n]<<endl;
}