[실버3] 백준 1463 - 1로 만들기

문제

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

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

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

입력

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

출력

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

Solution

다이나믹 프로그래밍

• 위의 문제는 다이나믹 프로그래밍의 대표적인 문제
• 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 방법
• 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

다이나믹 프로그래밍 사용 조건

• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

문제에 적용하기

DP의 핵심인 메모이제이션 방법을 이용하여 중복되어 계산되는 값을 저장해 효율을 높여준다

코드

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

const dp = new 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);
  }
}

console.log(dp[x]);