[알고리즘/백준/17626] Four Squares(Nodejs, DP)

문제

---

https://www.acmicpc.net/problem/17626

17626번: Four Squares

 

풀이

---

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let N = +fs.readFileSync(filePath).toString().trim();

const dp = Array.from({ length: N + 1 }).fill(0);
// dp[i]는 제곱수의 합으로 i를 만드는 최소 개수
dp[1] = 1;
let minCnt = 0;

for (let i = 2; i <= N; i++) {
  minCnt = Number.MAX_SAFE_INTEGER;
  for (let j = 1; j * j <= i; j++) {
    const tmp = i - j * j; // n에서 제곱수 빼주기
    minCnt = Math.min(minCnt, dp[tmp]);
  }

  dp[i] = minCnt + 1; // 제곱수 1개 더해주기
}

console.log(dp[N]);

어떤 자연수를 제곱수의 합으로 나타내는 문제이다. 최소 몇 개의 제곱수로 n이 될 수 있는지를 찾아야 한다.

 

처음에는 아래와 같이 완전탐색으로 푸려고 했지만 시간초과로 실패했다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let n = +fs.readFileSync(filePath).toString().trim();
let answer = Number.MAX_SAFE_INTEGER;

function DFS(L, sum) {
  if (L > 4) return;
  if (sum > n) return;
  if (sum === n) {
    answer = Math.min(answer, L);
  } else {
    for (let i = 1; i < Math.floor(Math.sqrt(n)) + 1; i++) {
      DFS(L + 1, sum + i ** 2);
    }
  }
}

DFS(0, 0);
console.log(answer);

 

이때 이전 값을 활용해 다음에 이용하는 메모이제이션을 쓸 수 있으면 좋겠다고 생각했는데, 이럴 때 다이나믹 프로그래밍을 사용할 수 있다.

dp[i]는 문제에서 요구하는대로 i를 만들 수 있는 최소 제곱수의 개수이다. 

i보다 작은 제곱수들을 구하고, 해당 제곱수를 뺀 값을 만드는 최소 제곱수의 개수를 살펴봤을 때 그 최소값에 1을 더하는 방식이다.

 

예를 들어, 26의 경우를 보자. 26보다 작은 제곱수는 1, 4, 9, 16, 25가 있다. 그러면 26에서 이 제곱수를 뺀 dp[25], dp[22], dp[17], dp[10], dp[1] 중에서 가장 작은 값에 +1을 해준 값이 dp[26]이 된다. 제곱수는 단 하나의 제곱수로 만들 수 있기 때문이다.