1699 제곱수의 합

백준 1699 제곱수의 합 https://www.acmicpc.net/problem/1699

어떤수 N (10만 이하의 자연수)에 대하여 제곱수가 되는 최소 항을 찾는 문제이다.

D[N]을 N의 제곱수의 합의 최소 항개수 라고 정의하였을 때
자연수중에 한 수의 제곱으로만 이루어진 제곱수에 D[N]을 계산하는 방식으로 문제를 해결하였다.

예를들어 4라는 숫자는 2의제곱으로 하나의 항을 가지는 제곱수이다.
이다음에 오는 5는 당연히 제곱수가 아니기 때문에 4+1로 2개의 항을 가진다.
그다음 수 6도 4+1+1로 구성되겠다.

이렇게 N을 1부터 N까지 증가시키며 D[N]을 채워나간다.
물론 계속 제곱수를 발견한다음 1씩 더해가면 안된다.

12라는 숫자를 보면 가장 가까운 제곱수인 9에 3을 더하는 경우로
9+1+1+1 : 4개의 항이 나온다. 하지만 4+4+4로 더 작은 3개의 항이 존재한다.

그러므로 D[N]에 지금까지 구했던 D[N]을 더해 더 작은 항에 대한 경우도 고려를 한다.

D[N+M] = min(D[N+M], D[N] + D[M])

#include <cstdio> #include <cmath> #define min(a,b) ((a<b)?a:b) bool soonsu(int num){     int x = (int)sqrt((double)num);     if (x*x == num)         return true;     return false; } int main(){     int N;     int D[100001] = { 0 };     scanf("%d", &N);     for (int n = 1; n <= N; n++){         if (soonsu(n)){            //순수 제곱수             D[n] = 1;             for (int m = 1; n + m <= N; m++){                 if (D[n + m] > 0)                     D[n + m] = min(D[n + m], D[n] + D[m]);                 else                     D[n + m] = D[n] + D[m];             }         }     }     printf("%d\n",D[N]);     return 0; } d Colored by Color Scripter

cs

더 깔끔한 점화식을 사용한 사람이 많았지만 이것도 방법이니까...