BOJ 1699번 :: 제곱수의 합

#문제

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

1699번: 제곱수의 합

 

#작성 코드

#include <iostream>
using namespace std;
 
int n;
int dp[100001];
    //[i] : j를 만드는 방법의 수 
 
int main(){
    // n입력
    cin>>n;
    // dp배열을 1로만 이루어진 제곱수의 합(maximum case)으로 초기화한다. 
    for(int i=0; i<=n; i++){
        dp[i] = i;
    }
    
    for(int i=1; i<=n; i++){
        for(int j=1; j*j<=i; j++){
            dp[i] = min(dp[i], dp[i-j*j]+1);
        }
    }
    
    cout<<dp[n] <<'\n';
    return 0; 
}

##

n보다 작거나 같은 숫자들에 대해, 제곱수의 합의 최소 개수를 갱신해나가면서 답을 구해주어야 한다.

각 i에 대해, 제곱수의 합으로 i를 구성하는 경우 maximum case는 1+1+...+1의 케이스이다.

-> dp[i] = i로 초기화해준다.