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

🔴 문제

1로 만들기 2

🟡 Sol

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

const db = Array.from({ length: n + 1 }, (v) => 0);

db[2] = 1;
db[3] = 1;

let result = '';

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]);

while (n !== 1) {
  result += n + ' ';
  if (n % 6 === 0) {
    const min = Math.min(db[n - 1], db[n / 3], db[n / 2]);
    if (db[n / 3] === min) n /= 3;
    else if (db[n / 2] === min) n /= 2;
    else if (db[n - 1] === min) n -= 1;
  } else if (n % 3 === 0) {
    const min = Math.min(db[n - 1], db[n / 3]);
    if (db[n / 3] === min) n /= 3;
    else if (db[n - 1] === min) n -= 1;
  } else if (n % 2 === 0) {
    const min = Math.min(db[n - 1], db[n / 2]);
    if (db[n / 2] === min) n /= 2;
    else if (db[n - 1] === min) n -= 1;
  } else {
    n -= 1;
  }
}

console.log(result + 1);

🟢 풀이

DP 기본유형(개어려움)
1로만들기와 동일한 유형인데 1로만들기 위해 거쳐간 숫자를 같이 적어줘야 한다.
그래서 정답을 먼저 구해준 후 while 문을 돌면서 거쳐간 숫자를 구해준다.

🔵 Ref