[백준] 1463. 1로 만들기 (dp)

www.acmicpc.net/problem/1463

1463번: 1로 만들기

보자마자 dfs 풀이가 생각났으나 dp로 풀어보려고 했다.

a,b,c 대신에 배열을 쓰면 좀 더 깔끔할 듯하다.

최종 dp[n]에 들어가는 수가 1로 시작해서 n을 만들 수 있는 경우의 수이니 n에서 1을 만드는 것과 방법의 수가 같다.

각각의 방법으로 현재 수 i를 만드는 방법 중 최소의 계산 횟수를 넣어준다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int answer;
	static int n;
	static int[] dp;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		dp=new int[n+1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[1]=0;
		for(int i=2;i<=n;i++) {
			int a=Integer.MAX_VALUE;
			int b=Integer.MAX_VALUE;
			int c=Integer.MAX_VALUE;
			if(i%2==0) {
				a=dp[i/2]+1;
			}
			if(i%3==0) {
				b=dp[i/3]+1;
			}
			c=dp[i-1]+1;
			dp[i]=Math.min(a, b);
			dp[i]=Math.min(dp[i], c);
		}
		System.out.println(dp[n]);
	}
}