[BaekJoon] 17626번 Four Squares

▶ 문제 : https://www.acmicpc.net/problem/17626

17626번: Four Squares

 

▶ 코드 :

 

const input = require('fs').readFileSync('BaekJoon/testcase.txt').toString().trim().split('\n');

let n = Number(input[0]);

const dp = Array(50001);
dp[0] = 0;
dp[1] = 1;


for(let i = 1; i < n+1; i++){
    let count = 0;
    let temp = i;
    while(temp != 0){
        const num = parseInt(Math.sqrt(temp)) ** 2;
        temp -= num;
        count += 1;
    }
    dp[i] = count;

    for(let j = 1; j < parseInt(Math.sqrt(i)) + 1; j++){
        dp[i] = Math.min(dp[i], dp[j ** 2] + dp[i - (j**2)]);
    }
}

console.log(dp[n])

 

▶ 문제 풀이 :

1. DP 와 관련하여 조금은 생각도 길게해야하고 버거워 검색을 해보았다.  

 

[참조] : https://velog.io/@kyy00n/%EB%B0%B1%EC%A4%80-17626%EB%B2%88-Four-Squares

[백준] 17626번: Four Squares

2. 위의 사이트에서 Python 을 이용해 구현한 코드를 참고해 Javascript 코드로 변환해보며 방법을 이해해보았다.

3. 초기 1 ~ 50000까지의 숫자별 최소 라그랑주 수를 저장할 배열인 dp 를 선언하고 0과 1을 초기화하였다.

4. 이후 입력된 n 만큼 반복문을 순회한다. 

5. 내부에서는 count를 0으로 초기화하고, temp 변수에 i 값을 할당한다. 

6. 이후 temp 가 0이 될때까지 while문을 돌면서 num이라는 변수에 현재 temp 값의 제곱근의 제곱을 빼준다. 이때 count는 1을 증가시켜 temp에서 뺄 수 있는 가장 큰 제곱근의 제곱수를 뺐을때의 count를 dp에 저장한다.

7. 이렇게 우선적으로 count값을 구한뒤 for문을 이용해 1 ~ (i 의 제곱근 정수부의 제곱 + 1)까지 순회하면서 현재 dp에 저장된 값과 해당 수(i)를 만들 수 있는 제곱의 경우에 저장된 dp 값의 합을 비교하며 최소값을 탐색한 뒤 dp[i]를 업데이트한다. (물론 그대로일 수 있겠지)

8. 이렇게 반복문을 순회한 뒤 dp[입력 숫자]를 출력하면 끄읕 ~