[백준1463_자바스크립트(javascript)] - 1로 만들기

🔴 문제

1로 만들기

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const n = Number(fs.readFileSync(path));

const db = new Array(n+1).fill(0);

for (let i = 2; i <= n; i++) {
  db[i] = db[i - 1] + 1;
  if (i % 3 === 0) db[i] = Math.min(db[i], db[i / 3] + 1);
  if (i % 2 === 0) db[i] = Math.min(db[i], db[i / 2] + 1);
}

console.log(db[n]);

🟢 풀이

dp의 기본 유형이다.
x가 1인경우 연산 횟수는 0이니 2부터 n까지 반복한다.
2부터 n까지 반복하면서 i의 최소 연산횟수는 i-1에서 1을 빼준 연산횟수가 제일 최소라고 가정한다. 따라서 db[i] = db[i-1] + 1(1을 빼준 연산)이라고 가정한 뒤 만약 i가 3의 배수거나 2의 배수라면 최소값을 갱신해주면 된다. 여기서 중요한 부분은 큰 수로 나누어줘야 한다. 예를 들어 문제에서 6의 배수일 경우 6으로 나눌수 있다는 조건이 추가된다면 6으로 나누어 주는것이 3과 2로 나누어 주는 것 보다 연산 횟수가 적기 때문이다.

이렇게 큰 문제를 해결하기 위해 작은 문제를 호출하는 방법을 DP 라고 하며, 이를 재귀로 구현하게 되면 시간초과가 발생하는데 db라는 배열에 연산한 값을 저장함으로써 db[n]을 호출할 경우 해당 로직을 다시 수행하지 않고 배열에 저장한 값을 가져와 수행 시간을 줄일 수 있다. 이러한 기법을 메모제이션 이라고 한다.

🔵 Ref