백준1699 제곱수의 합

문제

해결방법

step1. 1,4,6,9같은 제곱수에 1을 넣어준다.

step2. 나머지 숫자들을 찾아준다.

for (a = 1; a <=sqrt(i); a++) {
#dp[i]를 구하고자한다.
#min( dp[i-1^2]+1, dp[i-2^2]+1, dp[i-3^2]+1....dp[i-sqrt(i)^2] ) 이다.
                if (dp[i - a * a] < minx)

                minx = dp[i - a * a];

            }

dp[i] = minx + 1;

코드

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int main()
{
    int input;
    int dp[100010];
    cin >> input;
    dp[1] = 1;
    int a;
    int minx;
    int i, j;
    for (i = 1; i <= sqrt(input); i++) {
        dp[i*i] = 1;
    }
    for (i = 2; i <= input; i++) {
        if (dp[i] == 1)
            continue;
        else {
            minx = 100001;
            for (a = 1; a <=sqrt(i); a++) {
                if (dp[i - a * a] < minx)
                    minx = dp[i - a * a];
            }
            dp[i] = minx + 1;
        }
    }
    cout <<dp[input];
    return 0;
}