백준 1463(Dynamic Programming)

▶1463 문제

 

▶ 문제풀이

- 동적 계획법 사용해야함 < fn(n) = fn(n-1) + fn(n-2) + ... + fn(0); >

점화식 : dp[n] = Math.min(dp[n-1], dp[n/2], dp[n/3]) + 1;

- 초기값 설정 : 위의 문제에서  1이 입력되었을 때 이미 1이기 때문에 0이 출력됨. (dp[1] = 0)

- dp[2] = dp[1] + 1 = 1;

- dp[3] = dp[1] + 1 = 1;

- dp[4] = dp[2] + 1 = 2;

- dp[5] = dp[4] + 1 = 3;

.....

- dp[10] = dp[9] + 1 = 3;

import java.io.*;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
	
		int[] dp = new int[num+1];
		dp[0] = dp[1] = 0;
		
		for(int i = 2; i <= num; i++) {
			dp[i] = dp[i-1] + 1;
			
			if(i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3]+1);
			if(i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2]+1);
		}
		
		System.out.println(dp[num]);
		br.close();
	}
}