[백준_1699] 제곱수의 합 ( DP - 자바스크립트 )

문제

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

1699번: 제곱수의 합

 

How to Solve ?

 

[1] DP

 

1 - 문제를 이해했는가?

 

 제곱 수들을 더해서 "num"을 구할 때 필요로 하는 최저의 개수를 출력하라. 라는 문제입니다.

 

2- 풀이 전략

 

풀이 방법을 도출 해내기 위해서, 24까지의 수를 제곱수의 합으로 구해보았습니다. 이러한 모든 경우의 수를 특정한 점화식을 세우지 않고 브루트포스를 할 경우 숫자가 커지면 값을 도출 할 수 없을 것 같다는 판단을 하게 되어 DP로 접근을 하게 되었습니다.

 

아래의 그림을 보면 찾을 수 있는 제가 찾은 패턴은 2가지가 있는데,

 

1) N의 제곱수가 나오면 1로 초기화가 된다.

2) N의 제곱수 + 4(2^2)의 배수라면  => 1 + 4로 나눈 값 

 

이였습니다. 

 

특정한 패턴을 찾았지만, 이에 대한 "점화식"을 세우는데 어려움을 겪었는데 결과적으로, 특정한 수가 어떤 수의 제곱근이라면 이전에 있던 에 저장된 값을 찾으면 된다는 결론이 나왔고 이를 통해서 다음과 같은 수식을 세울 수 있었습니다

 

DP[i] = Math.min ( DP[i], Dp[ i - Math.pow(j,2) ] + 1 ) 

즉, 현재 위치에서 특정한 값의 제곱근을 뺄 수 있는 상황이라면, 그 값을 뺀 위치에 있는 dp 값에서 1을 더하면 된다는 것 입니다.

 

 

 

전체 코드

function solve() {
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j < i; j++) {
    // 2^2 > 3 => 4가 3보다 크다는건 이전 제곱수의 값을 이용 할 수 없음을 의미
      if (Math.pow(j, 2) > i) {
        break;
      }
	// 그래서 dp[2](3-1)에 있는 값을 이용 
      dp[i] = Math.min(dp[i], dp[i - Math.pow(j, 2)] + 1);
    }
  }
  console.log(dp);
}

const n = 8;
// [ 0, 1, 2, 3, 4, 5, 6, 7]
const dp = Array.from({ length: n + 1 }, (v, i) => i);
solve();

// 1st loop => 1 < 1(j)^2 => true => pass

// 2nd loop => 2 < 1(j)^2 > false 

// dp[2] = Math.min(2, dp[1] + 1) => 2