제곱수의 합

문제

언어

  • JavaScript

문제 풀이 step 1

  • dp[n] = 자연수 n을 제곱수의 합으로 표현할 때 그 항의 최소 개수
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
  • 자연수 k를 생각해보겠습니다. 이때 dp[k-1], dp[k-2], … dp[1]에는 각 수를 나타낼 수 있는 제곱수의 합의 최소 항의 개수가 들어있습니다.
  • 그렇다면 dp[k]가 될 수 있는 경우는 아래와 같습니다.
    • dp[k] = dp[k - (1 * 1)] + 1
    • dp[k] = dp[k - (2 * 2)] + 1
    • …
    • dp[k] = dp[k - (k * k)] + 1
    • 단, index가 0보다 작아지는 경우는 제외해야 합니다. 쉬운 설명을 위해서 다 적어봤습니다.
  • 위의 경우만큼 나올텐데 1을 제외하고는 다른 수들은 본인을 제곱한 것이 본인이 되지 않기 때문에 경우의 수는 더 적게 나옵니다.
  • 우리가 구해야 하는 것은 항의 최소 개수이므로, 저 모든 경우들 중에서 값이 최소인 것이 정답이 됩니다.

후기

  • 문제를 다시 푸는 도중에 제곱 연산자인 ** 를 사용해봤는데,
    • 시간초과가 발생하는 것을 보아 Math.pow() 나 k * k 를 사용하는 것이 더 빠른 것 같습니다.

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	let n = parseInt(input[0]);

	// base
	const dp = [0, 1];
	for (let i = 2; i < n + 1; i++) {
		dp[i] = i;
		let k = parseInt(Math.sqrt(i)) + 1;

		for (; k > 0; k--) {
			if (i - k * k < 0) continue;
			dp[i] = Math.min(dp[i], dp[i - k * k] + 1);
		}
	}

	return dp[n];
};

console.log(solution(input));