[백준] 1699번: 제곱수의 합

문제

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

풀이

const fs = require('fs');
let N = fs.readFileSync('/dev/stdin').toString().trim() * 1;
let dp = new Array(N + 1).fill(0);
for (let i = 1; i <= N; i++) {
    dp[i] = i;
    for (let j = 1; j * j <= i; j++) {
        dp[i] = Math.min(dp[i], 1 + dp[i - j * j]);
    }
}

console.log(dp[N]);

dp[i]의 최대값은 1의 합으로 이루어진 조합이므로 i 가 된다.
메모제이션의 제곱 수를 i에서 뺀 값과 현재 메모제이션 값 중 최소 값을 dp[i]에 할당한다.

회고

처음에 dp[i] = 1 + dp[i - (Math.floor(Math.sqrt(i)) ** 2)]; 로 풀었더니
틀렸다고 나왔다.

반례로 753이 있는데
처음에 생각한 로직으로 하면 Math.floor(Math.sqrt(i)) 는 27이 나온다.
dp[753] = 1 + dp[753 - 729] = 1 + dp[24]
4 (729 + 16 + 4 + 4 = 753)

정답은 다음과 같다.
3 (625 + 64 + 64 = 753)

따라서 이전 제곱수들를 활용해서 값을 찾고 현재 메모제이션과 그 값을 비교해서
최소값을 메모해야한다.