첫 시도
- N이 10이라 완전탐색으로 가능 할 것 같지만 이전에 계산한 값을 다시 여러번 계산해야 하는것이 비효율적으로 느껴져 dp로 해결
- 정수 N을 1,2,3의 합으로 나타내는 문제기 때문에 1,2,3을 기저 사례로 설정하면 문제를 해결할 수 있음
- dp[num] = dp[num-1] + dp[num-2] + dp[num+3]
해결
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
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 T = Integer.parseInt(br.readLine());
for(int i = 0; i<T; i++){
int N = Integer.parseInt(br.readLine());
dp = new int[N+2];
System.out.println(dynamic_programming(N));
}
}
static int dynamic_programming(int num){
if(num < 3) return num;
if(num == 3) return 4;
dp[num] = dynamic_programming(num-1) + dynamic_programming(num-2) + dynamic_programming(num-3);
return dp[num];
}
}