합이 주어진 숫자 n과 같은 최소 제곱 수

모든 숫자는 완전제곱수의 합으로 나타낼 수 있습니다. 이 문제에서는 주어진 값을 나타내는 데 필요한 완전제곱항의 최소 개수를 찾아야 합니다.

값이 94이므로 95 =9 ² 입니다. + 3 ² + 2 ² + 1 ² . 따라서 답은 4가 됩니다.

아이디어는 1에서 시작하는 것입니다. 더 나아가 완전제곱수를 얻습니다. 값이 1~3일 경우 1로만 구성되어야 합니다.

입력 및 출력

Input:
An integer number. Say 63.
Output:
Number of squared terms. Here the answer is 4.
63 =72 + 32 + 22 + 1

알고리즘

minSquareTerms(value)

입력: 주어진 값입니다.

출력: 주어진 값에 도달하기 위한 최소 제곱 항 수입니다.

Begin
   define array sqList of size value + 1
   sqList[0] := 0, sqList[1] := 1, sqList[2] := 2, sqList[3] := 3

   for i in range 4 to n, do
      sqList[i] := i
      for x := 1 to i, do
         temp := x^2
         if temp > i, then
            break the loop
         else sqList[i] := minimum of sqList[i] and (1+sqList[i-temp])
      done
   done
   return sqList[n]
End

예시

#include<bits/stdc++.h>
using namespace std;

int min(int x, int y) {
   return (x < y)? x: y;
}

int minSquareTerms(int n) {
   int *squareList = new int[n+1];

   //for 0 to 3, there are all 1^2 needed to represent

   squareList[0] = 0;
   squareList[1] = 1;
   squareList[2] = 2;
   squareList[3] = 3;

   for (int i = 4; i <= n; i++) {
      squareList[i] = i; //initially store the maximum value as i

      for (int x = 1; x <= i; x++) {
         int temp = x*x;      //find a square term, lower than the number i
         if (temp > i)
            break;
         else squareList[i] = min(squareList[i], 1+squareList[itemp]);
      }
   }
   return squareList[n];
}

int main() {
   int n;
   cout << "Enter a number: "; cin >> n;
   cout << "Minimum Squared Term needed: " << minSquareTerms(n);
   return 0;
}

출력

Enter a number: 63
Minimum Squared Term needed: 4