문제

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

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

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

입력

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

출력

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

풀이

다이나믹 프로그래밍 문제를 처음 풀어봐서 다른 사람의 풀이를 봐도 이해하는데 한참을 걸렸다...

dp라는 배열을 만들고 각 index값에 index값을 구하는 최솟값을 넣는다.

ex)
dp[1] = 1을 구하는 최솟값 : 1
dp[2] = 2를 구하는 최솟값 : dp[1] + 1
dp[3] = 3을 구하는 최솟값 : dp[3-1] + 1 (1 + 2), dp[3/3] + 1 (1 x 3) 중 작은 수
dp[4] = 4를 구하는 최솟값 : dp[4-1] + 1 (1 + 3), dp[2/2] + 1 (2 x 2) 중 작은 수
dp[5] = 5를 구하는 최솟값 : dp[5-1] + 1
...

이를 통해 점화식을 구할수 있는데,

-1의 경우
dp[n-1] + 1 (1을 뺐기에 연삿횟수 1을 더한다)
3으로 나눠지는 경우
dp[n/3] + 1 (3를 나눴기에 연삿횟수 1을 더한다)
2로 나눠지는 경우
dp[n/2] + 1 (2를 나눴기에 연삿횟수 1을 더한다)

1) 3이나 2로 나누어 떨어지지 않을 경우 dp[n] = dp[n] + 1
2) 3으로 나눠질 경우 dp[n/3] + 1 값과 dp[n] + 1값을 비교해 더 작은 수가 dp[n]이 된다.
3) 2로 나눠질 경우 dp[n/2] + 1 값과 dp[n] + 1값을 비교해 더 작은 수가 dp[n]이 된다.

코드

var fs = require('fs');
let n = +fs.readFileSync('./input.txt').toString().trim();

function solution() {
	const dp = new Array(n + 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 / 3] + 1, dp[i]); //3으로 나누어 떨어질때의 최솟값
		}
		if (i % 2 === 0) {
			dp[i] = Math.min(dp[i / 2] + 1, dp[i]); //2로 나누어 떨어질때의 최솟값
		}
	}

	console.log(dp[n]);
}

solution();