LeetCode 279 - Perfect Squares (Medium)

문제

LeetCode - 279번

풀이 과정

양의 정수 n 에 대해서 최소 개수의 완전 제곱수로 표현하는 방법을 찾는 문제입니다.

예를 들어 12 는 2의 제곱인 4 를 3번 더해서 만들 수 있습니다.

만약 구하고자 하는 수 n 을 이용해서 dp(n) = n을 완전 제곱수로 표현하기 위한 최소 개수 라고 한다면
다음과 같은 점화식을 세울 수 있습니다.

dp(n) = min(dp(n-X)+1), 이때 X 는 n을 넘기지 않는 왼전 제곱 수

예를 들어 `dp(13)` 은 9를 완전 제곱수로 1개 선택하고 `dp(13-9) + 1 = dp(4) + 1` 과 같이 표현할 수 있는 것입니다.
따라서 위와 같이 점화식을 세워주면 `동적 계획법` 으로 문제를 해결할 수 있습니다.

코드

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
  const dp = new Array(n + 1).fill(Infinity);

  dp[0] = 0;

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

  return dp[n];
};