[1463번] 정수를 1로 만들기

---

---

✅ DP

1) 주어진 입력까지 dp 배열 생성
2) dp[i] = i에서 1로 만드는 데 걸리는 최소 연산 횟수
3) 기저 사례 : dp[0] = 0, dp[1] = 0
4) 점화식

dp[i] = dp[i-1] + 1 //1을 빼는 연산
dp[i] = dp[i/2] + 1 //2를 나누는 연산
dp[i] = dp[i/3] + 1 //3을 나누는 연산

dp[i] = dp[i-1] - 1; //1로 뺴는 건 가능한 모든 경우

//3으로 나누는 것이 우선순위가 더 높다. 
-> 라고 생각했지만 배열 안에 들어있는 값은 경우의 수의 값이므로 else-if를 쓰면 틀린다. 
//dp[i]는 이전에 계산한 min 값이 되겠다.
if(i%3 == 0) Math.min(dp[i], dap[i/3]+1);
if(i%2 == 0) Math.min(dp[i], dap[i/2]+1);

동전 2와 달리 if 문을 사용하므로 배열의 범위를 벗어나는 것에 대해서는 고려하지 않아도 된다.
구하지 못하는 경우도 존재하지 않는다.

---

✅ 시도 2 실패 코드

import java.util.Scanner;

public class Main {
	static int[] dp;

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

		dp[0] = 0;
		dp[1] = 0;

		for (int i = 2; i <= n; i++) {
			if (i % 3 == 0) {
				dp[i] = Math.min(dp[i - 1] + 1, dp[i / 3] + 1);
			}
			if (n % 2 == 0) {
				dp[i] = Math.min(dp[i - 1] + 1, dp[i / 2] + 1);
			} else {
				dp[i] = dp[i - 1] + 1;
			}
		}

		System.out.println(dp[n]);

	}
}

---

✅ 시도 2 코드

모든 경우에 포함될 수 있는 경우에는

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

이렇게 최상단에 먼저 적어주자.

import java.util.Scanner;

public class Main {
	static int[] dp;

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

		dp = new int[n + 1];

		dp[0] = 0;
		dp[1] = 0;

		for (int i = 2; i < n + 1; 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[n]);
	}
}

---