[백준] 1463번 - 1로 만들기 (nodejs)

문제

1463번: 1로 만들기

 

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

풀이

하나의 숫자 다음에 3개의 연산을 할 수 있으므로 처음에는 한 노드에 3개의 노드가 달려있는 그래프 탐색 문제인 줄 알았다. 최단거리를 찾는 문제와 비슷하므로 BFS로 풀면 될 것이라고 생각했는데 그러면 중복되는 계산이 너무 많다.

 

예를 들어 X=12일 때 4까지 가는 과정이 무수히 많다면 그 중 계산횟수가 가장 최소인 것을 dp[4]에 저장하고, 다시 X=4일때의 계산횟수를 구하는 식으로 과정을 쪼개면 중복되는 계산을 줄일 수 있을 것이다.

따라서 DP로 풀기로 했다.

 

dp[x]라는 것은 x가 1이 되기까지 얼마나 연산을 해야하는지 연산 횟수를 의미하는 것이다.
dp[1] = 0인데, 1은 1이 되기까지 필요한 연산횟수가 0이기 때문이다.
따라서 x=2부터 구하면 된다.
for문으로 x=2인 경우부터 1씩 증가하며 이전 연산횟수 (dp[x-1])을 이용해 다음 연산횟수 (dp[x])를 구해준다.

(bottom-up 방식)

 

(왜 bottom-up 방식으로 푸냐면 작은 수의 합은 작은 수라는 것을 확신할 수 있지만, top-down 방식은 어떻게 하면 최종 결과가 작을지 확신할 수 없기 때문이다.)

규칙을 찾아보면

X       1을 빼는 경우 dp[x]
2       1
3       2
4       3
...     dp[x-1] + 1

X       2로 나누는 경우 dp[x]
2       1
4       2
6       3
8       dp[4] + 1
...     dp[x/2] + 1

2로 나누는 것에서 주목할 점이 있다. X=6일 때 2로 나눠서 연산 횟수가 +1이 됐다. X는 3이 되었다. X=3의 연산횟수는 dp[3]라고 할 수 있다.
dp[6] = dp[6/2] + 1이다. dp[3]은 이전에 구해놓은 것을 사용하면 된다.

마찬가지 원리로 3으로 나누는 경우의 점화식은 dp[x/3] + 1이 된다.

X       3으로 나누는 경우 dp[x]
...     dp[x/3] + 1

그런데 만약 6처럼 2와 3의 공배수인 경우 어떤 수로 우선 나눠야 할까? 최소 연산횟수를 구하는 것이 목적이므로
if(x % 2 === 0)과 if(x % 3 === 0) 두 가지 경우의 dp[x]를 모두 구하고 그 중 최소값을 dp[x]에 저장하면 된다.

 

 

코드

const fs = require('fs');
const X = Number(fs.readFileSync('input.txt').toString().trim());

function solution() {
  const dp = Array(X + 1).fill(0);

  for (let i = 2; i <= X; i++) {
    dp[i] = dp[i - 1] + 1;

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

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

  return dp[X];
}

console.log(solution());