백준 1463번 1로 만들기

내가 푼 코드

가 아니라 구글링한 것. 다이나믹 프로그래밍은 생전 처음 배워본거라 문제에 적용하려니 아리송했다. 근데 풀어보고 생각해보니 어렴풋이 잡힌다.

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

let N = Number(input[0]);

let arr = new Array(N+1).fill(0);

for(let i=2; i <= N; i++) {
    arr[i] = arr[i-1] + 1;

    if(i%2 === 0) {
        arr[i] = Math.min(arr[i], arr[i/2] + 1);
    }

    if(i%3 === 0) {
        arr[i] = Math.min(arr[i], arr[i/3] + 1);
    }
}

console.log(arr[N]);

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

이 세가지를 적절히 사용해 1을 만드는데 연산 횟수가 가장 작아야 한다.

길이가 N+1인 배열arr를 만든다. 여기서 arr배열의 index는 숫자를 뜻한다. 해당인덱스의 요소는 그걸 만드는 최솟값이다.

2와3으로 떨어지지 않을 수 있으니 가장먼저 arr의 i번째 요소를 arr[i-1](i에서 1을뺀 것)에 1을 더해준다(-1을 했으니 연산횟수에 +1을 해야 하기에)
2로 나누어 떨어진다면 arr[i]는 arr[i](위에 i-1을 해준 횟수)와 arr[i/2]를 해준 횟수 +1중 작은 수로 한다.
3도 마찬가지다.

참고 블로그
참고 블로그