첫 시도
- 시간제한이 0.15초 -> 약 10^7
- N이 10^6이라 O(N)으로 해결해야 하는 문제
- dp 구현이 미숙해 실패
해결
- for문을 이용한 바텀업 -> O(N), 통과
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] 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%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]);
}
}
- 재귀를 이용한 탑다운 -> O(?), 시간 초과
- 시간이 빠듯한 문제는 탑다운으로 풀지 않는 것이 좋겠다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int[] dp;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
dp = new int[N+1];
System.out.println(dp(N));
}
static int dp(int num){
if(num == 1) return 0;
if(dp[num] > 0) return dp[num];
dp[num] = dp(num-1)+1;
if(num % 2 == 0) {
dp[num] = Math.min(dp[num],dp[num/2]+1);
}
if(num % 3 == 0){
dp[num] = Math.min(dp[num],dp[num/3]+1);
}
return dp[num];
}
}