[JavaScript/DP] 백준 실버 1 : 12852 - 1로 만들기 2

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

12852번: 1로 만들기 2

---

📌 작성한 코드 

// 12852
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim();

const N = Number(input);
const dp = Array.from({ length: N + 1 }, () => new Array(2));
dp[1][0] = 0;
dp[1][1] = "";

for (let i = 2; i <= N; i++) {
    dp[i][0] = dp[i - 1][0] + 1;
    dp[i][1] = `${i} ` + dp[i - 1][1];

    if (i % 2 === 0) {
        if (dp[i][0] > dp[i / 2][0] + 1) {
            dp[i][0] = dp[i / 2][0] + 1;
            dp[i][1] = `${i} ` + dp[i / 2][1];
        }
    }
    if (i % 3 === 0) {
        if (dp[i][0] > dp[i / 3][0] + 1) {
            dp[i][0] = dp[i / 3][0] + 1;
            dp[i][1] = `${i} ` + dp[i / 3][1];
        }
    }
}

console.log(dp[N][0]);
console.log(dp[N][1] + "1");

📌 설명

- 정의 : dp[i] = i번까지 도달하는데 사용한 최소 연산의 수

- 점화식 : dp[i] = min(dp[i-1],dp[i/2],dp[i/3])+1

 

점화식 도출 방법

숫자 i에 도달하는 방법은 3가지이다.

`i - 1에 1 더하기`, `i / 2에 2 곱하기`, `i / 3에 3 곱하기` -> 이 3개 중 최소의 연산 횟수 + 1이 dp[i]가 된다. 

 

경로 저장하기 

dp[i]를 업데이트하기 위해 세 개의 연산 중 최솟값을 찾았을 때 해당 최솟값이 지나가는 경로가 될 것이다. 그래서 dp[i]까지 가는 경로를 저장하기 위해서 dp를 이차원 배열로 생성하여 dp[i][1]에는 경로를 저장해준다.

-> 지금 도달한 i + 확정된 경로 

 

✅ 성공