[백준] 1699번 제곱수의 합 C++

문제 출처: https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

N 은 최대 N개의 1^2 합으로 표현 가능하다.

따라서 dp[i] = i;로 초기화 한 뒤

dp[i] = min(dp[i],dp[i-j*j]+1); 을 통해 구할 수 있다.

dp[0] = 0

dp[1] = 1^2

dp[2] = 1^2 + 1^2

dp[3] = 1^2 + 1^2 + 1^2

dp[4] = 1^2 + 1^2 + 1^2 + 1^2 ==> dp[4] = min( dp[4] , dp[4-2*2]+1);  dp[4] = 1

.

.

dp[8] = min (dp[8] , dp[8-2*2]+1);  dp[8] = 2

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include <string>

using namespace std;


int dp[100001];


int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    

    int N; cin >> N;
    
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        dp[i] = i;
        for (int j = 2; j * j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }


    cout << dp[N];
    
  



}