[백준 17626] Four Squares with Node.js

문제 링크

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

17626번: Four Squares

풀이

const solve = n => {
  const dp = new Array(n+1).fill(0);
  dp[1] = 1;
  for (let i=2; i<=n; i++) {
    let min = 4;
    for (let j=1; j*j<=i; j++) {
      min = Math.min(min, dp[i-j*j]);
    }
    dp[i] = min + 1;
  }
  console.log(dp[n]);
};

const n = +require('fs').readFileSync('/dev/stdin').toString().trim();
solve(n);

dp[N]은 더해서 N이 되는 제곱수 개수의 최솟값이다.

따라서 임의의 자연수 n(N ≤ n²)에 대해서 N = n²라면 dp[N] = 1이다.

 

N은 제곱수들의 합이므로,

dp[N] = dp[n²] + dp[N-n²] = dp[N-n²] + 1이 성립한다.

 

그러나 어떤 자연수 n을 골라야 dp[N]의 최솟값을 구할 수 있는지 알 수 없기 때문에

N ≤ n²인 모든 n에 대해서 dp[N-n²]을 구해서 최솟값을 갱신한다.

그리고 그 값에 1을 더하면 최종적으로 dp[N]의 최솟값을 구할 수 있다.

 

 

예시)

N = 27

n의 후보 : 1, 2, 3, 4, 5

 

- n = 1

dp[27] = dp[1] + dp[26] = dp[26] + 1 = 2

(dp[26]에 대해서도 n의 후보 1, 2, 3, 4, 5가 있고

dp[1]+dp[25], dp[4]+dp[22], dp[9]+dp[17], dp[16]+dp[10], dp[25]+dp[1] 중 최솟값을 찾아야 하는데

반복문을 통해 순차적으로 dp를 채워왔으므로, dp[27]을 구하고자 하는 시점에 이미 dp[26]이 구해져 있는 상태이다.)

 

- n = 2

dp[27] = dp[4] + dp[23] = dp[23] + 1 = 5

 

- n = 3

dp[27] = dp[9] + dp[18] = dp[18] + 1 = 3

 

- n = 4

dp[27] = dp[16] + dp[11] = dp[11] + 1 = 4

 

- n = 5

dp[27] = dp[26] + dp[1] = dp[1] + 1 = 2

 

따라서 dp[27] = 2이다.