[백준] 17626번: Four Squares - Node.js (자바스크립트)

1. 문제 ㅡ 17626번: Four Squares (난이도: Silver III)

17626번: Four Squares

2. 풀이 ㅡ Node.js (자바스크립트)

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

const getMinNeeded = targetNumber => {
  const dp = Array.from({ length: targetNumber + 1 }, () => 0);
  dp[1] = 1;

  for (let i = 2; i <= targetNumber; i++) {
    let min = Number.MAX_SAFE_INTEGER;

  // j 제곱이 i 보다 작거나 같을 떄까지 
    for (let j = 1; j * j <= i; j++) {
      min = Math.min(min, dp[i - j * j]);
    }

    dp[i] = min + 1;
  }

  return dp[targetNumber];
};

console.log(getMinNeeded(target));

2-1. 풀이 설명

입력값으로 주어진 정수(target)를 만들기 위해 필요한 최소한의 제곱값을 구하는 문제다. Brute Force 알고리즘으로 접근하기에는 시간 제한이 0.5초였기에 Dynamic Programming을 사용해서 풀었다.

 

Dynamic Programming 구현을 위해 사용되는 점화식은 어렵지 않다. 26을 예시로 들었을 때, 26을 구하기 위해 필요한 최소한의 제곱수는 (26 - 1 = )25를 구현하기 위한 최소한의 제곱수(1) + 1이다. 따라서 j 제곱이 i 보다 작거나 같을 때까지 반복문을 돌면서 i를 만들기 위해 필요한 최소한의 제곱수를 구하고, dp[i] 의 값을 최소한의 제곱수로 업데이트 해줬다. 

 

반복문이 끝난 후에는 dp배열의 targetNumber번째 값을 출력했다.