[백준 BOJ] 1463 - 1로만들기 (node.js)

문제

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.

X가 2로 나누어 떨어지면, 2로 나눈다.

1을 뺀다.

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

시간제한

0.15초

입력

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

출력

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

알고리즘 분류

다이나믹 프로그래밍

다이나믹 프로그래밍을 이용하여 해결할 수 있는 문제이다.

먼저 X - 1 일때 점화식을 아래와 같이 나타낼 수 있다.

X	값
2	1
3	2
4	3
5	4
6	5
…	...
X	X - 1

DP[X] = DP[X - 1] + 1 로 나타낼 수 있다. +1 은 이것 자체로 연산 1회를 추가함을 의미한다.

그리고 X % 2 === 0 일때 점화식은 아래와 같이 나타낼 수 있다.

X	값
2	1
3	3
4	2
5	5
6	3
…	…
X	X / 2

DP[X] = DP[X / 2] + 1 로 나타낼 수 있다. 마찬가지로 +1 은 연산 1회를 추가함을 의미한다.

그리고 X % 3 === 0 일때 점화식은 아래와 같이 나타낼 수 있다.

X	값
2	1
3	1
4	4
5	5
6	2
…	…
X	X / 3

DP[X] = DP[X / 3] + 1 로 나타낼 수 있다.

이제 이 정보들을 기반으로 주어진 수 X에 대한 배열을 만들고 최소값을 찾으면 된다.


const fs = require('fs');
const inputData = fs.readFileSync('/dev/stdin').toString().trim();

const solution = (X) => {
  let dp = new Array(X + 1).fill(0);

	// 알아낸 점화식의 정보를 바탕으로 배열을 채워준다.
  for (let i = 2; i < dp.length; i++) {
    dp[i] = dp[i - 1] + 1;

    if (i % 3 === 0) {
			// dp[i] 와 dp[i / 3] + 1 중 더 작은값을 선택한다.
      dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    }

    if (i % 2 === 0) {
			// dp[i] 와 dp[i / 2] + 1 중 더 작은값을 선택한다.
      dp[i] = Math.min(dp[i], dp[i / 2] + 1);
    }
  }

  return dp[X];
}

console.log(solution(Number(inputData)))

[백준 BOJ] 1463 - 1로만들기 (node.js)

acmicpc - 1로만들기 (node.js)