백준 1463번 1로 만들기(JAVA,DP)

<풀이방식>

특정 숫자는 3으로만 나눠지거나 2로만 나눠지거나 2,3 모두 나눠지거나 2,3 둘다 나눠지지 않는 4가지로 나눌 수 있다.
3으로만 나눠진다면 3으로 나누거나, 1을 빼거나 2가지 액션이 가능하다.
이 중의 최소값을 선택해야하므로

if(i%3 ==0 && i%2!=0) {
	dp[i] = Math.min(dp[i/3],dp[i-1]) +1;
}

처음에 2,3 모두 나눠지는 경우에는 어떤 수로 나눠도 상관이 없다고 생각해서 계속 틀렸는데 알고보니 이것도 2로 나눠지거나 3으로 나눠지거나 1빼거가 3가지 액션중에 최소값을 선택했어야 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int [] dp = new int [n+1];

		//초기값 세팅
		if(n>=1)
			dp[1] = 0;
		if(n>=2) 
			dp[2] = 1;
		if(n>=3) {
			for(int i = 3 ; i < n+1; i++) {
				//3으로만 나눠지는경우
				if(i%3 ==0 && i%2!=0) {
					dp[i] = Math.min(dp[i/3],dp[i-1]) +1;
				}
				//2로만 나눠지는 경우
				else if(i%2 ==0 && i%3!=0) {
					dp[i] = Math.min(dp[i/2],dp[i-1]) + 1;
				}
				//2,3모두 나눠지는 경우는 전부 체크
				else if((i%3 ==0 && i%2==0)) {
					int min = Math.min(dp[i/3], dp[i/2]);
					dp[i] = Math.min(min,dp[i-1]) + 1;
				}
				//둘다 아닌경우면 1을 뺀 숫자의 최소값에 1더함
				else if(i%3 !=0 && i%2 !=0){
					dp[i] = dp[i-1]+1;
				}
			}
		}

		System.out.println(dp[n]);
	}


}