[BOJ 12852] 1로 만들기 2 (nodejs)

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

이전에 풀었던 1로 만들기 문제에서 경로를 추적하여 출력하는 코드가 추가된 문제이다.
처음에 top-bottom 코드에서 거꾸로 dp 배열에서 1씩 적은 숫자를 만날때마다 배열에 넣고 출력하였는데 stackoverflow가 발생하였다.
문제의 N은 10^6 까지인데 10^5부터 발생하길래 bottom-up 으로 푸니까 해결함.

핵심아이디어

dp 배열 이외에 경로를 추적하는 배열을 하나 더 두었다.

만약 입력값이 8이면 다음인덱스 = pre[8]이 되고, 반복문이 돌때마다 갱신된 인덱스값을 출력하면 8 4 2 1이 출력 된다.

주의할 점은 기존에 내가 풀었던 코드는 다음과 같다.

for(let i = 2; i <= input; i++){
    d[i] = d[i - 1] + 1;
    pre[i] = i - 1;
    if(i % 2 ===0){
        d[i] = Math.min(d[i], d[i / 2] + 1);
        pre[i] = i / 2;
    }
    if(i % 3 === 0 && d[i] > d[i / 3] + 1){
        d[i] = Math.min(d[i], d[i / 3] + 1);
        pre[i] = i / 3;
    }
}

pre 배열을 확인해보면 [0, 0, 1, 1, 2, 4, 2, 6, 4, 3, 5] 이다.
입력값이 10을 예로 들면 답은 10 9 3 1 인데, 위와 같이 풀면 추적을 10 5 4 2 1 순으로 하게 된다.

따라서 다음과 같이 코드를 고쳐야 한다.

for(let i = 2; i <= input; i++){
    d[i] = d[i - 1] + 1;
    pre[i] = i - 1;
    if(i % 2 === 0 && d[i] > d[i / 2] + 1){
        d[i] = d[i / 2] + 1;
        pre[i] = i / 2;
    }
    if(i % 3 === 0 && d[i] > d[i / 3] + 1){
        d[i] = d[i / 3] + 1;
        pre[i] = i / 3;
    }
}

반드시 d[i] > d[i/2 or 3 ] + 1 조건을 만족시켜야만 pre 배열을 갱신할 수 있는데 이유는 무엇일까?

pre 배열을 확인해보면 [0, 0, 1, 1, 3, 4, 3, 6, 4, 3, 9]로 위와 다른 것을 알 수 있다.

인덱스를 앞에서부터 증가시키며 달라지는 구간을 확인해보자.

idx 0 d 0 pre 0
idx 1 d 0 pre 0

idx 2 d 1 pre 1
idx 3 d 1 pre 1
idx 4 d 2 pre 3(4 3 1 / 4 2 1)
idx 5 d 3 pre 4
idx 6 d 2 pre 3(6 3 1 / 6 2 1)
idx 7 d 3 pre 6
idx 8 d 3 pre 4
idx 9 d 2 pre 3
idx 10 d 3 pre 9(10 9 3 1 / 10 5 4 2 1)

=> 이때는 pre값이 전 인덱스를 가리키고 if문으로 들어가 나눗셈 연산을 하면 안된다는 것을 알 수 있는데 if문 안에서 빼는 경우보다 나누는 경우의 d값이 더 적은 경우에만 경우의 수를 줄일 수 있기 때문이다. 그런데 기존의 코드는 d[i]값에 관계없이 항상 나눌 수 있으면 나누기 때문에 2로 나눠떨어지거나 3으로 나눠떨어질때마다 경로를 잘못 추적하게 된다.

참고로 이 아이디어는 다른 문제에서도 시간 복잡도를 줄이는데 도움을 준다고하니 잘 알아두자.

전체코드

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

const d = new Array(input+1).fill(0);
const pre = new Array(input+1).fill(0);
d[1] = 0;

for(let i = 2; i <= input; i++){
    d[i] = d[i - 1] + 1;
    pre[i] = i - 1;
    if(i % 2 === 0 && d[i] > d[i / 2] + 1){
        d[i] = d[i / 2] + 1;
        pre[i] = i / 2;
    }
    if(i % 3 === 0 && d[i] > d[i / 3] + 1){
        d[i] = d[i / 3] + 1;
        pre[i] = i / 3;
    }
}

console.log(d[input]);
let cur = input;
const answer=[];
while(1){
    answer.push(cur);
    if(cur===1){
        break;
    }
    cur=pre[cur];
}

console.log(answer.join(' '))

//   1 2 3 4 5 6 7 8 9 10 index
// 0 0 1 1 3 4 3 6 4 3 9  pre