BOJ - 1699번 제곱수의 합

http://acmicpc.net/problem/1699

1699번: 제곱수의 합

 

며칠동안 못 푼 문제다.

 

최소 몇개의 제곱수로 표현 가능한가? 를 찾는 문제다.

 

일단 DP[i] = i로 초기화 한다. 왜냐 1을 i개 더하는게 최댓값이니까

 

그리고 제곱수를 작은것부터 가져와서 생각한다.

 

제곱수를 k, 해당 수를 N이라고 한다면

 

DP[N] 이랑 DP[N-k]+1 중에 작은 것으로 DP[N]에 다시 값을 넣어주면 된다.

 

코드는 다음과 같다.

 

/* acmicpc.net - 1699번 제곱수의 합 */

#include <stdio.h>
#include <math.h>

int DP[100001];

void init() {

    int i;
    for (i = 0; i < 100001; i++) DP[i] = i;
}

int min(int a, int b) {

    if (a < b) return a;
    else return b;
}

void calDP() {

    int i, j, k;

    for (i = 2; i < (int)sqrt(100001); i++) {
        k = i * i;
        for (j = k; j < 100001; j++) DP[j] = min(1 + DP[j - k], DP[j]);
    }
}

int main() {
    int N;
    init();
    calDP();
    scanf("%d", &N);
    printf("%d\n", DP[N]);
    return 0;
}