백준 1463번 1로 만들기 - node.js

해당 포스팅은 백준 1463번 1로 만들기 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.

---

문제

1. 문제 설명

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

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.
연산을 사용하는 횟수의 최솟값을 출력하시오.

2. 입력

첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.

3. 출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

풀이

풀이 방법

연산을 최소화하기 위해서는

• 1부터 X까지의 숫자들의 연산을 최소화하고
• 이 부분합들을 이용해 X의 연산의 최솟값을 구해야 한다.

따라서 해당 문제는 DP 문제이다. 이 때 X는 최대 10^6이므로 바텀업으로 구현한다.

---

예제

예제를 통해 자세하게 설명하겠다. X가 10이라고 가정해보자.
연산은 아래 3가지가 가능하다.

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

어떤 연산이 최적인지 판별하기 위해서는 이전의 값을 참고해야 하므로 메모이제이션을 해야한다.

따라서 loop를 돌리면서

• 먼저 1을 뺀다 연산을 수행한다.

  memo[i] = memo[i-1] + 1;

• 그 다음 i가 3으로 나뉘어질 때 현재 memo[i]와 memo[i/3] + 1의 연산 횟수 중 작은 값으로 memo[i]를 업데이트한다.

  9의 경우 memo[8]+1과 memo[3] + 1의 연산 횟수 중 작은 값으로 업데이트 한다.

  memo[i] = Math.min(memo[i], memo[i/3] + 1);

• 그 다음 i가 2로 나뉘어질 때 현재 memo[i]와 memo[i/2] + 1의 연산 횟수 중 작은 값으로 memo[i]를 업데이트한다.

  4의 경우 memo[3]+1과 memo[2] + 1의 연산 횟수 중 작은 값으로 업데이트 한다.

  memo[i] = Math.min(memo[i], memo[i/2] + 1);

위의 과정을 거치면 dp(10)일 때의 memo는 아래와 같다.

[
  0, 0, 1, 1, 2,
  3, 2, 3, 3, 2,
  3
]

각각의 인덱스는 각 숫자의 연산의 최솟값이다. 우리가 구하고자 하는 것은 10의 최솟값이므로 memo[X]를 하면 된다.

---

전체 코드

const input = require('fs').readFileSync('/dev/stdin').toString()
const X = Number(input)

function dp(n, memo=[0,0]) {
    let i = 2;
    while (i <= n) {
        memo[i] = memo[i-1] + 1;
        if (i % 3 === 0) {
            memo[i] = Math.min(memo[i], memo[i/3] + 1);
        }
        if (i % 2 === 0) {
            memo[i] = Math.min(memo[i], memo[i/2] + 1);
        }
        i++;
    }
    return memo[n];
}

console.log(dp(X))