Baekjoon 1699번 제곱수의 합

문제

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

걸린 시간

-

풀이

TypeScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map((s: string) => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const n: number = parseInt(input());
const dp: number[] = Array(n+1).fill(Number.POSITIVE_INFINITY);
dp[0] = 0;

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

별 생각없이 그리디로 문제를 풀어 제출했더니 틀렸습니다를 받았다.

예제를 손으로 풀어보니 모든 경우를 조사해야하는 문제임을 알게 되었고, 특정 값에서의 최소 항의 개수를 메모이제이션 or 타뷸레이션 하면 시간안에 문제를 풀 수 있을 것 같았다.

이 문제는 dp 배열이 1차원이라 점화식을 세우기가 쉬워 반복 dp 로 풀이했다.