문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

예제

예제 입력 1

1
2
7

예제 출력 1

1
2
4

예제 입력 2

1
2
1

예제 출력 2

1
2
1

예제 입력 3

1
2
4

예제 출력 3

1
2
1

예제 입력 4

1
2
11

예제 출력 4

1
2
3

예제 입력 5

1
2
13

예제 출력 5

1
2

내 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const input = +require("fs").readFileSync("/dev/stdin").toString().trim();

const DP = Array.from({ length: input + 1 }, (_, i) => i);

for (let i = 4; i <= input; i++) {
  for (let j = 1; j <= Math.sqrt(i); j++) {
    const sqrt = Math.sqrt(i);
    if (sqrt === parseInt(sqrt)) {
      DP[i] = 1;
    } else {
      DP[i] = Math.min(DP[i], DP[i - j ** 2] + 1);
    }
  }
}

console.log(DP[input]);
  • 처음에는 단순히 초기값을 가지고 다음값을 구하는 식으로만 했었는데, 이렇게 할 경우 최소항을 비교하여 저장하면서 진행할 수 없다고 판단하여 2중 for문을 사용하였다.
  • 그 결과, 각 DP 마다 해당 index의 제곱근을 빼준 숫자의 DP에 +1 해준 것과 현재 DP를 비교했다.

ex) input = 18이라면, DP[18] = 18인 상태로 시작한다.

  1. j = 1 인 경우, DP[17] + 1 = 3이므로, DP[18] = 3를 저장한다.
  2. j = 2 인 경우, DP[14] + 1 = 4이므로, 이전 값을 그대로 둔다.
  3. j = 3 인 경우, DP[9] + 1 = 2 이므로, DP[18] = 2를 저장한다.
  4. j = 4 인 경우, DP[2] + 1 = 3 이므로 이전 값을 그대로 둔다.

j는 제곱근 이전 까지만 순회를 하므로 순회를 종료하고 DP값을 출력한다.

따라서, DP[18] = 2 로 (9+9) 이렇게 답을 구할 수 있다.