자바스크립트로 합이 n이 되는 최소 개수의 완전제곱수 찾기

문제 이해하기

양의 정수 num을 유일한 인자로 받는 자바스크립트 함수를 작성해야 합니다.

이 함수는 입력값과 합이 같아지도록 여러 완전제곱수를 더하는 조합을 찾아야 하며, 이때 가능한 한 적은 개수의 완전제곱수를 사용해야 합니다.

예를 들어 입력값이 다음과 같다면 −

const num = 123;

출력은 다음과 같아야 합니다 −

const output = 3;

그 이유는 123 = 121 + 1 + 1, 즉 11² + 1² + 1²처럼 세 개의 완전제곱수로 표현할 수 있지만, 두 개 이하의 완전제곱수로는 표현할 수 없기 때문입니다.

접근 방식: 동적 계획법(DP)

이 문제는 전형적인 동적 계획법(Dynamic Programming) 문제입니다. 특정 숫자에 대한 답을 그보다 작은 숫자들의 답을 활용해 도출할 수 있기 때문입니다.

코드를 살펴보기 전에, 먼저 작은 숫자들에서 나타나는 일반적인 패턴을 이해해 보겠습니다. 처음 여섯 개 숫자에 대한 결과는 다음과 같습니다 −

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

위 패턴에서 알 수 있듯이, 각 숫자의 답은 앞선 숫자들의 결과에 완전제곱수를 더하는 조합을 반복적으로 시도하여 얻어집니다. 예를 들어 6의 답은 4(= 2²)를 뺀 값인 2의 답(2)에 1을 더한 3이 됩니다.

알고리즘 동작 원리

1. 크기가 num + 1인 배열을 만들고 모든 값을 0으로 초기화합니다. 여기서 arr[i]는 "숫자 i를 만드는 데 필요한 최소 완전제곱수 개수"를 의미합니다.
2. num 이하의 모든 완전제곱수(i²)를 차례대로 순회합니다.
3. 각 완전제곱수 i²에 대해 배열의 i² 위치부터 끝까지 순회하면서, arr[j]를 arr[j - i²] + 1과 비교하여 더 작은 값으로 갱신합니다.
4. 모든 순회가 끝나면 arr[num]이 곧 정답이 됩니다.

예제 코드

다음은 전체 구현 코드입니다 −

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

즉, 123은 121(11²) + 1(1²) + 1(1²)의 세 개 완전제곱수로 표현할 수 있으며, 이것이 가능한 최소 개수입니다. 이 알고리즘의 시간 복잡도는 O(n × √n)으로, n이 큰 경우에도 효율적으로 동작합니다.