백준 1699번 : 제곱수의 합

  원래 백준의 단계별 문제의 [분할정복]을 다 풀려고 했는데 뒤 쪽 문제가 너무 어려워서 포기하고 알고리즘 분류에서 [다이나믹 프로그래밍] 시리즈를 풀기로 했다. 

 

  기존의 냅색 문제와 비슷하다. 모든 수는 1을 자기 자신만큼 더해서 표현할 수 있으므로 termCnt[i] = i를 기본으로 둔다. 이후 for문을 통해 j * j를 빼가면서 할당되어 있는 termCnt[i] 와 termCnt[i - j * j] + 1 중 작은 값을 termCnt[i]에 할당한다. termCnt[i - j * j] + 1에서 1을 더한 이유는 j * j가 하나의 항을 차지했기 때문이다.

#include <stdio.h>
#include <iostream>
 
using namespace std;

int termCnt[100004];

int main()
{
    int n;
    cin >> n;
    
    termCnt[1] = 1;
 
    for(int i = 1; i <= n; i++)
    {
        termCnt[i] = i;
    }
    
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; i - j * j >= 0; j++)
        {
            termCnt[i] = min(termCnt[i], termCnt[i - j * j] + 1);
        }
    }
    
    cout << termCnt[n];
 
    return 0;
}