❗ 단순 반복문, 조건문으로는 최소 횟수 를 산출할 수 없음!
❗ 무조건 큰 수로 나눠버리는게 최선이 아님!!!
// 너무 단순하게 생각한 반복문
int cnt = 0;
while (N != 1) {
if (N%3 == 0) N = N/3;
else if (N%2 == 0) N = N/2;
else N -= 1;
cnt++;
}
🔑 인덱스가 0부터 입력된 수까지 모든 수를 나타내는 배열을 생성하고, 각각 1이 되는 최소횟수를 값으로 가진다.
💡 Top-Down은 재귀함수
(출처 : https://odysseyj.tistory.com/19)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static int d[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
br.close();
d = new int[N+1];
System.out.println(dp(N));
}
public static int dp(int N) {
if (N == 1)
return 0;
if (d[N] > 0)
return d[N];
d[N] = dp(N-1) +1;
if(N%3 == 0)
d[N] = Math.min(d[N], dp(N/3)+1);
if(N%2 == 0)
d[N] = Math.min(d[N], dp(N/2)+1);
return d[N];
}
}
💡 Bottom-Up은 반복문을 이용한 방식으로, base case부터 값을 다 찾으면서 원하는 값에 도달하는 것
(출처 : https://odysseyj.tistory.com/19)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
br.close();
int dp[] = new int[N+1];
dp[0] = 0;
dp[1] = 0;
for(int i=2;i<=N;i++) {
dp[i] = dp[i-1] + 1;
if(i%2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1);
if(i%3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1);
}
System.out.println(dp[N]);
}
}
DP를 스스로 풀지 못해 결국 구글링해버렸다..
그래도 어떤 식으로 풀이 코드를 이해하긴 했으니, 조금씩 구글링을 줄여가면서 DP를 풀어보자.
(근데 둘 다 출력시간은 어마어마하네...)