1699 제곱수의 합

문제 분석

알고리즘: DP

주어진 수에 대해 제곱수의 합으로 나타낼 수 있는 항의 최소 개수를 구하는 문제다.

먼저 모든 자연수는 1²으로 나타낼 수 있다. 즉, 4가 주어질 때 1² +1² +1² +1², 총 4개의 항으로 나타낼 수 있지만 이는 최대항의 개수다.

하지만 우리가 구하고자 하는 것은 최소항의 개수이므로 4를 2²으로, 1개의 항으로 나타낼 수 있다. 또, 최대항의 개수와 최소항의 개수를 비교하여 더 작은 수를 메모제이션 한다.

예를 들어, 주어진 수 N이 7이라고 할 때 7까지 최소 항을 구해보자.

N	최소항	최소항 수
1	12	1
2	12 + 12	2
3	12 + 12 + 12	3
4	22	1
5	22 + 12	2
6	22 + 12 + 12	3
7	2 2 + 12 + 12 + 12	4

위 표를 토대로 최소항의 수를 공식화하여 풀어보면 다음과 같이 해석할 수 있다.

N	최소항	최소항 수 공식 (N -i2) + 1	최소항 수
1	12	(1 - 12)+ 1	1
2	12 + 12	(2 - 12)+ 1	2
3	12 + 12 + 12	(3 - 12) + 1	3
4	22	(4 - 22) + 1	1
5	22 + 12	(5 - 22) + 1	2
6	22 + 12 + 12	(6 - 22) + 1	3
7	2 2 + 12 + 12 + 12	(7 - 22) + 1	4

즉, 1부터 N까지의 수를 순환하면서 최소항의 개수를 메모제이션 하는 동적 프로그래밍 알고리즘을 이용할 수 있고 이를 점화식으로 나타내면 다음과 같다.

여기서 i ** 2 는 i² 을 표현한다.

DP[N] = Math.min(DP[N], DP[N - i ** 2] + 1);

풀이

const n = +require('fs').readFileSync('dev/stdin');
const dp = new Array(n + 1).fill(0);

for (let i = 1; i <= n; i++) {
  dp[i] = n;
  for (let j = 1; j ** 2 <= i; j++) {
    dp[i] = Math.min(dp[i], dp[i - j ** 2] + 1);
  }
}

console.log(dp[n]);