백준 1699 제곱수의 합

algorithm : DP

 

해설

dp는 최솟값을 구하는 문제이기 때문에 답이 될 수 없는 INF를 초기값으로 한다

 

DP [i] : i번째 수를 만들었을 때 제곱수 항의 최소 개수

1	2	3	4	5	6	7	8	9	10
1	2	3	2	3	INF	INF	INF	INF	INF

i가 6일 경우에는 5에서 1의 제곱수인 1을 더하여 4를 만들거나 2에서 2 * 2의 제곱수를 더하여 6을 만드는 3 만드는 2가지 경우중 제일 작은 3이 dp [6]이 된다.

이처럼  i를 만들수 있는 경우의 수 중 만들었을 때 가장 작은 값이 dp [i]가 된다

#include<bits/stdc++.h>
#define LM 200000+10
#define INF 199999999
using LL = long long;
using namespace std;

int N;

int dp[LM];

void input(){
    scanf("%d",&N);
}

void DP(){
    for(int i = 1 ; i <= N ; i++)
        dp[i] = INF;
    for(int i = 0 ; i <= N ; i++){
        for(int j = 1 ; j <= 1000  && 0 <= i - j * j ; j ++)
            dp[i] = min(dp[i],dp[i - j * j] + 1);
    }
    printf("%d",dp[N]);
}

int main(){
    //freopen("input.txt","r",stdin);
    input();
    DP();
    return 0;
}