[C++] 백준 1699번 제곱수의 합

 

다이나믹 프로그래밍 문제입니다.

 

자연수 N을 만들때 제곱수들로 최소 몇개의 항으로 만들 수 있는지 찾는 문제입니다.

 

먼저 1제곱으로 만들 때의 수를 저장하고

다음 2제곱과 1제곱으로 만들 때의 수를 저장합니다.

다음 3제곱과 2제곱과 1제곱으로 만들 때의 수를 저장합니다.

....

이와 같은 방식으로 반복하여서 결과값을 도출해냅니다.

 

코드로 나타내면 아래와 같습니다.

memo[j] = min(memo[j], memo[j - (i*i)] + 1);

이전에 저장된 값과 현재 저장하고 있는 값중 수가 더 적은것을 저장하는 방식입니다.

 

#include <iostream>
#include <algorithm>
#define MAX 987654321
using namespace std;

int main(int argc, char *argv[])
{
   int n;
   int memo[100010] = { 0, };
   cin >> n;

   for (int i = 1; i < 100010; ++i) {
      memo[i] = MAX;
   }
   for (int i = 1; i <= n; ++i) {
      if (i*i > n) {
         break;
      }
      int j = i * i;
      for (; j <= n; ++j) {
         memo[j] = min(memo[j], memo[j - (i*i)] + 1);
      }
   }
   cout << memo[n] << endl;
   return 0;
}