[백준][DP] 1463 1로 만들기

https://www.acmicpc.net/problem/1463

이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있다. 

i번째 값을 만들 수 있는 경우는

i-1 번째에서 1을 더하는 경우

i%2 == 0인 경우에서 1을 더하는 경우

i%3 == 0인 경우에서 1을 더하는 경우이다. 

이 세가지 경우를 for 문을 이용하여 반복하여 해결한다. 

	import java.util.Scanner;
	public class Problem1463 {
	static int[] d = new int[100];
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	sc.close();
	int result = one(N);
	System.out.println(result);
	}
	public static int one(int N) {
	int[] dp = new int[N + 1];
	dp[1] = 0;
	for (int i = 2; i <= N; i++) {
	// i-1 번째에 1을 더하는 경우
	dp[i] = dp[i - 1] + 1;
	// i%2 == 0인 경우에서 1을 더하는 경우
	if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
	dp[i] = dp[i / 2] + 1;
	}
	// i%3 == 0인 경우에서 1을 더하는 경우
	if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
	dp[i] = dp[i / 3] + 1;
	}
	}
	return dp[N];
	}
	}

view raw Problem1463.java hosted with ❤ by GitHub