JavaScript에서 합이 n이 되는 가장 작은 완전제곱수

유일한 인수로 num과 같은 양수를 취하는 JavaScript 함수를 작성해야 합니다.

함수는 더할 때 입력으로 제공된 숫자를 제공하는 완전제곱수의 조합을 찾아야 합니다. 가능한 한 적은 수의 완전제곱수를 사용하도록 해야 합니다.

예를 들어 -

입력 번호가 -

const num = 123;

그러면 출력은 다음과 같아야 합니다. -

const output = 3;

123 =121 + 1 + 1

이것은 이전 숫자의 결과를 기반으로 특정 숫자에 대한 결과에 도달할 수 있는 고전적인 동적 프로그래밍 문제입니다.

코드로 바로 넘어가기 전에 먼저 일반적인 패턴을 이해하고 실제로 DP가 솔루션을 고안하는 데 도움이 될 것입니다.

6개의 5개 숫자에 대한 결과는 다음과 같습니다. -

1 --> 1 (1)
2 --> 2 (1 + 1)
3 --> 3 (1 + 1 + 1)
4 --> 1 (4)
5 --> 2 (4 + 1)
6 --> 3 (4 + 1 + 1)

이것은 우리가 성공적인 결과를 얻으려면 이전 결과에서 조합을 시도하고 시도해야 함을 분명히 보여줍니다.

예시

다음은 코드입니다 -

const num = 123;
const sumSquares = (num) => {
   let arr = new Array(num + 1).fill(0);
   arr[1] = 1;
   for(let i = 1; i * i <= num; i++) {
      for(let j = i * i; j < arr.length; j++) {
         if(arr[j] == 0) {
            arr[j] = arr[j - (i * i)] + 1;
         } else {
            arr[j] = Math.min(arr[j - (i * i)] + 1, arr[j]);
         }
      }
   };
   return arr[num];
};
console.log(sumSquares(num));

출력

다음은 콘솔 출력입니다 -

3