[백준, node.js] 1463번 "1로 만들기" 문제 해결방법

[백준, node.js] 1463번 "1로 만들기" 문제 해결방법

문제

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

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

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

입력

출력

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

예제 입력/출력 1

// 입력
2

// 출력
1

예제 입력/출력 2

// 입력
10

// 출력
3

소스코드

다이나믹 프로그래밍(DP, 동적계획법)을 통해 쉽게 해결이 가능한 문제이다. 정수 X에 사용할 수 있는 연산은 1을 뺀 경우, 2로 나누는 경우, 3으로 나누는 경우가 있다.

우선 이 문제를 풀기 위해 정수 X - 1을 했을 경우 정수 X - 1을 해결한 최솟값임을 알 수 있다. 아래와 같이 DP[x] = DP[x-1] + 1의 점화식으로 표현할 수 있다.

1을 빼는 경우 DP[x] = DP[x-1] + 1 점화식

1을 빼는 경우가 최솟값일 경우도 있겠지만, 2나 3으로 나눠질 경우 훨씬 더 최솟값에 가까운 수가 될 것이다. 2로 나눠질 경우 아래와 같이 DP[x] = DP[x/2] + 1의 점화식으로 표현할 수 있다.

2로 나눠질 경우 DP[x] = DP[x/2] + 1의 점화식

3으로 나눠질 경우 아래와 같이 DP[x] = DP[x/3] + 1의 점화식으로 표현할 수 있다.

3으로 나눠질 경우 DP[x] = DP[x/3] + 1의 점화식

결과적으로 아래와 같은 점화식으로 찾은 값들 중 최솟값을 찾아내면 된다.

• DP[x] = DP[x-1] + 1
• DP[x] = DP[x/2] + 1
• DP[x] = DP[x/3]

const fs = require('fs');
let count = Number(fs.readFileSync('./dev/stdin').toString());
const dp = new Array(count + 1).fill(0);

for (let i = 2; i < dp.length; i++) {
  dp[i] = dp[i-1] + 1; // 1을 뺀 경우의 최솟값

  if (i % 3 === 0) {
    dp[i] = Math.min(dp[i], dp[i/3] + 1) // 3으로 나눴을 경우의 최솟값
  }
    
  if (i % 2 === 0) {
    dp[i] = Math.min(dp[i], dp[i/2] + 1) // 2로 나눴을 경우의 최솟값
  }
}

console.log(dp[count]);