백준_1로 만들기_1463

//알고리즘

1. 동적프로그래밍(dp)

2. 1부터 주어진값까지 dp테이블을 만들어 계산함.

3. 3으로 나누어떨어질 때, 2로 나누어떨어질 때, 아니면 1을 빼는데 이 순서대로 하면 답이 안나올 수도 있음.

 -> 역순으로 시작해야 최소연산의 횟수를 구할 수 있음.(아이디어가 필요한 문제인듯)

 

import java.util.Scanner;

public class 백준_1로만들기_1463 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		int[] ans = new int[N+3];

		ans[1] = 0;
		ans[2] = 1;
		ans[3] = 1;

		for (int i = 4; i <= N; i++) {
			ans[i] = 1 + ans[i - 1];
			if (i % 2 == 0) {
				if (ans[i] > ans[2] + ans[i / 2]) {
					ans[i] = ans[2] + ans[i / 2];
				}
			}
			if (i % 3 == 0) {
				if (ans[i] > ans[3] + ans[i / 3]) {
					ans[i] = ans[3] + ans[i / 3];
				}
			}

		}

		System.out.println(ans[N]);
	}

}