백준 1699 JavaScript
수정하기
문서 생성 2022-01-27 10:42:31 최근 수정 2022-04-29 20:53:15
문제
풀이
Dynamic Programming을 이용해 풀이를 하면,
DP라는 배열에 해당 인덱스 값을 표현할 수 있는 제곱수 항의 최소 개수를 넣는다고 가정하자.
예를 들어, 숫자 "24"의 경우는 DP[24]에 24를 제곱수들의 합으로 표현할 때 그 항의 최소 개수가 들어가게 된다.
이 최소 개수를 구하려면 어떻게할까?
24를 예로 들면 24보다 작은 제곱수들은 1, 4, 6, 9, 16이 있다.
이 제곱수들을 이용해 합을 구성할 수 있는 방법은 다음 4가지 중 하나일 것이다.
(24 - 1²)의 최소 개수 + 1(1²)(24 - 2²)의 최소 개수 + 1(2²)(24 - 3²)의 최소 개수 + 1(3²)(24 - 4²)의 최소 개수 + 1(4²)
따라서 위 식은 아래와 같이 나올 수 있다. 이 값들 중 최소인 경우를 구하면 된다.
DP[24] = DP[23] + 1DP[24] = DP[20] + 1DP[24] = DP[15] + 1DP[24] = DP[8] + 1
제곱수들의 합으로 표현할 때 가장 큰 경우는 모두 1의 제곱으로 이루어진 경우일 것이다. 따라서 최대개수는 그 수 자신이다. 우선 그 값으로 DP 배열을 초기화를 해준다.
24 = 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1² + 1²
그 다음, 2부터 순회를 시작한다.
const readFileSyncPath = require('path').basename(__filename).replace(/js$/, 'txt');// const readFileSyncPath = '/dev/stdin';const N = Number(require('fs').readFileSync(readFileSyncPath).toString().trim());// 1의 제곱으로만 이루어진 제곱수 항의 개수 = 값 자신const DP = Array.from({ length: N + 1}, (v, i) => i);// 2부터 N까지 순회for (let i = 2; i <= N; i++) {// 어떤 수의 제곱이 해당 값보다 작은 경우 까지for (let j = 2; j * j <= i; j++) {// 해당 값에 제곱을 뺀 경우 최소 개수에 + 1을 한 것과 -> (해당 값 - 어떤 수(j)의 제곱)의 항의 개수에 어떤 수(j)의 제곱을 더한 것// 현재 해당 값 중 더 작은 것으로 변경DP[i] = Math.min(DP[i], DP[i - j * j] + 1);}}console.log(DP[N]);