본문 바로가기
Algorithm/BaekJoon[Java]

백준 1463(Dynamic Programming)

by 씨니 2022. 3. 19.
728x90

▶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();
	}
}
728x90

'Algorithm > BaekJoon[Java]' 카테고리의 다른 글

백준 11727  (0) 2022.03.20
백준 11726  (0) 2022.03.19
백준 10991, 10992 (별찍기)  (0) 2022.03.18
백준 2438, 2439, 2440, 2441, 2442, 2445, 2446 (별찍기)  (0) 2022.03.17
백준 10818  (0) 2022.03.17