package baekjoon;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class b9095 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for(int tc = 0; tc < T; tc++) {
int n = Integer.parseInt(br.readLine());
int dp[] = new int [11];
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for(int i = 4; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
bw.write(dp[n]+"\n");
}
bw.flush();
}
}
다이나믹 프로그래밍 <dp>
dp[n] = n을 1,2,3의 합으로 나타낼 수 있는 경우의 수
dp[1] = 1, dp[2] = 2 (1+1 / 2) , dp[3] = 4 (1+1+1 / 1+2 / 2+1 / 3 )
dp[4] = 7 ( 1+1+1+1 / 1+1+2 / 1+2+1 / 1+3 / 2+2 / 2+1+1 / 3+1 )
dp[4] = dp[3] + dp[2] + dp[1] ; 점화식
n = 1,2,4일 때의 경우의 수 fix
'Problems & Solutions' 카테고리의 다른 글
19941 햄버거 분배 (0) | 2022.08.05 |
---|---|
7795 먹을 것인가 먹힐 것인가 (0) | 2022.07.30 |
11441 합 구하기 (0) | 2022.07.26 |
1058 친구 (0) | 2022.07.25 |
1244 스위치 켜고 끄기 (0) | 2022.07.25 |