문제1463. 1로 만들기
다이나믹 프로그래밍의 바텀업 방식으로 풀었다.
1부터 n까지 모든수의 최솟값을 dp에 저장하는 방식으로 풀었다.
모든 수를 저장하는 이유는 가장 큰 값인 3으로 나눈다고 하여 최소 횟수를 보장하지 않기 때문이다.
//계산이 쉽도록 n+1로 생성
int[] dp = new int[n+1];
//현재 수에서 -1, /2, /3 했을 때
//해당 숫자를 만들 수 있는 최소 횟수 +1 = 현재 수를 만들 수 있는 횟수
//3개중 최솟값을 저장
for (int i = 2; i <= n; 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);
}
}
System.out.println(dp[n]);