(1699)(DP) 백준 제곱수의 합

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

풀이

---

dp를 이용해서 풀기로 한다. N의 범위가 100,000이므로 100,000의 제곱근의 반올림 수인 317개의 배열을 선언해 주기로한다.

dp[100001] = { 0 };

arr[317]  = { 0 };

그리고 dp 배열을 모두 -1로 초기화 해주기로 한다. 그 이유는 0과 -1의 구분을 짓기 위해서인데 초기화 했던 -1로 계속 값이 남아 있는 경우는 이전까지의 

제곱수로 만들수 없다는 것을 의미하게끔 하기 위해 

또, dp[0]값과 초기화 값이 0으로 동일하다면 min함수를 쓰기가 어려워지기 때문에 if(dp == -1) 조건을 두어

사전에 거르기 위함이다.

dp[0] = 0개

dp[1] =   1개    /     1^2 

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

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

dp[4] =    1개    /    min(dp[3] + 1개(1^2) or  dp[0] + 1개(2^2))

dp[5] =    2개   /    dp[4] + 1개(1^2)    

dp[6] =    3개    /    dp[5] + 1개(1^2)

dp[7] =     4개    /    dp[6] + 1개(1^2)

dp[8] =    2개    /    min(dp[7]    or   dp[4]  + 1개(2^2))

.

.

.

이런식으로 비교해주면서 최소값을 저장해 나가면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
 
#define min(a,b) a<b ? a:b
 
int main() {
    int N;
    int cnt = 1;
    int arr[317] = { 0 };
    int dp[100001];
 
    memset(dp, -1, sizeof(dp));
    
    scanf("%d", &N);
    for (int i = 1; i <= (int) sqrt(N); i++) {
        arr[i] = cnt*cnt;
        cnt++;
    }
 
    
    dp[0] = 0;
    
    for (int i = 1; i <= N; i++) {
        for (int j=1; j <= (int) sqrt(i); j++) {
            if (i >= arr[j] && dp[i - arr[j]] != -1) {
                if (dp[i] == -1) dp[i] = dp[i - arr[j]] + 1;
                else dp[i] = min(dp[i], dp[i - arr[j]] + 1);
            }
        }
    }
 
    printf("%d\n", dp[N]);
    
    return 0;
}