Baekjoon 1699번: 제곱수의 합

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

Q.어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=3²+1²+1²(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=2²+2²+1²+1²+1²(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.
주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

동적계획법 문제.
1부터 검사하되 i에서 1의 제곱, 2의 제곱…을 뺐을 때 어떤 숫자가 나오는지로 거꾸로 생각해 풀어야 한다.

`// https://www.acmicpc.net/problem/1699 Baekjoon No.1699 제곱수의 합
#include <iostream>
#include <math.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  int dp[n+1] = {0,};
  for (int i = 1; i<=n; i++) {
    for (int j = 1; j*j <= i; j++) {
      //j제곱을 빼며 거꾸로 탐색, 비어있을 경우 그냥 넣고 아니면 기존값과 비교
      if(dp[i] > dp[i-j*j]+1 || dp[i] == 0) {
        dp[i] = dp[i-j*j]+1;
      }
    }
  }
  cout << dp[n];
  return 0;
}
`