[BOJ/1699] 제곱수의 합

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

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

 

사용 알고리즘

- DP

 

풀이

- d[i] = i를 제곱수의 합으로 나타냈을 때, 필요한 항의 최소 개수

- d[i] = min(d[i - (j * j)] + 1) (1 <= i <= j * j)

 

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/1699.cpp

#include <cstdio>   int d[100003]; int a[100003];   int main(void) {     int n; scanf("%d", &n);     for (int i = 1; i <= n; ++i) {         for (int j = 1; j * j <= i; ++j) {             if (d[i] == 0) {                 d[i] = d[i - (j * j)] + 1;             }             else {                 if (d[i] > d[i - (j * j)] + 1) d[i] = d[i - (j * j)] + 1;             }         }     }     printf("%d\n", d[n]);     return 0; } Colored by Color Scripter

cs