백준 silver 3 - 1463 1로 만들기(Javascript)

1463 - 1로 만들기

풀이과정

정답은 맞췄지만 개선이 필요함을 느낌

문제 자체는 dp를 이용하면 크게 어렵지 않았는데, N으로 부터 1로 가는 과정에서 i를 만드는데 필요한 연산횟수인 dp[i]를 구하기 위해서는 i+1과 2*i, 3*i번째 값들의 최소값을 가져와야 했다.
그래서 Math.min(dp[i + 1], dp[2 * i], dp[3 * i])라는 연산이 필요한데, dp배열의 원소의 개수를 N개로 설정할 경우 i+1, 2*i, 3*i가 undefined이기 때문에 NaN이 리턴된다. 그래서 dp배열의 범위를 3*N + 1로 설정해 문제를 해결하긴 했는데, 이건 또 너무 메모리 낭비가 될 것 같았다.

개선방법

결국 아래의 부분에서 Math.min 메소드의 인자로 undefined가 들어가기 때문에 문제인 건데,

for (let i = N - 1; i >= 1; i--) {
  dp[i] = 1 + Math.min(dp[i + 1], dp[2 * i], dp[3 * i]);
}

이 부분을 아래처럼 개선할 수 있었다.

for (let i = N - 1; i >= 1; i--) {
  const filtered = [dp[i + 1], dp[2 * i], dp[3 * i]].filter(v => v !== undefined);
  dp[i] = 1 + Math.min(...filtered);
}

이렇게 되면 최초에 dp배열을 초기화할 때 N+1범위까지만 설정하더라도 오류가 생기지 않는다.

정답코드

const filePath = process.platform === 'linux' ? 'dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString();

const N = Number(input);
const dp = [...Array(3 * N + 1)].map(v => 1000000);
dp[N] = 0;
for (let i = N - 1; i >= 1; i--) {
  dp[i] = 1 + Math.min(dp[i + 1], dp[2 * i], dp[3 * i]);
}
console.log(dp[1]);