DP 개념이 처음에는 무슨 말인지 이해가 안되었는데, 계속 보다보니 이해가 됐다 , 내가 푼 것은 아니고
https://st-lab.tistory.com/132 이분의 블로그에 있는 내용을 베껴왔다. 그런데 혼자 풀라고 했으면 절대 못 풀었을 것 같다.
원리는 이렇다 , 재귀를 이용해서 계산하게 되면 어마어마한 양의 계산을 수행해야한다.
하지만 이전에 계산했던 내용을 저장해놓고 , 거기서부터 계산을 하게 되면 계산해야 되는 양을 훨씬 줄일 수 있다.
import java.util.Scanner;
public class Main {
static Integer[] dp;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
dp = new Integer[N + 1];
dp[0] = dp[1] = 0;
System.out.print(recur(N));
}
static int recur(int N) {
if (dp[N] == null) {
// 6으로 나눠지는 경우
if (N % 6 == 0) {
dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
}
// 3으로만 나눠지는 경우
else if (N % 3 == 0) {
dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
}
// 2로만 나눠지는 경우
else if (N % 2 == 0) {
dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
}
// 2와 3으로 나누어지지 않는 경우
else {
dp[N] = recur(N - 1) + 1;
}
}
return dp[N];
}
}
'PS > 백준' 카테고리의 다른 글
백준 - 01타일 ( Java ) (0) | 2023.11.16 |
---|---|
백준 - 학점 계산 (0) | 2023.11.14 |
백준 - 수학은 체육과목 입니다 (0) | 2023.11.12 |
백준 - 삼각형 외우기 (0) | 2023.11.12 |
백준 - 알고리즘 수업 - 피보나치 수1 (0) | 2023.11.12 |
댓글