원리:
1 = {1}
2 = {1+1, 2}
3 = {1+1+1, 1+2, 2+1, 3}
=> 4 = 1+3, 2+2, 3+1
=> 1인 케이스에 3을 더하고, 2인 케이스에 2를 더하고, 3인 케이스에 1을 더하면 된다!
=> 4 = {1+3} + {1+1+2, 2+2} + {1+1+1+1, 1+2+1, 2+1+1, 3+1}
= dp[1] + dp[2] + dp[3]
= 7
=> dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
import java.io.*;
import java.util.*;
public class Main {
static int dp[] = new int[11]; //1~10
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = in.nextInt(); //테스트 케이스
dp[1] = 1; //1 = {1}
dp[2] = 2; //2 = {1+1, 2}
dp[3] = 4; //3 = {1+1+1, 1+2, 2+1, 3}
for(int i=4; i<=10; i++)
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]; //점화식
for(int i=0; i<t; i++) {
int n = in.nextInt();
System.out.println(dp[n]);
}
}
}
참고 사이트click
2023-03-07
