이전의 계산한 값들을 이용해서 그 다음 값을 구해야 하는 경우 dynamic programming으로 접근해야 한다는 생각이 들었다. 문제에서 n의 최대값이 11이라고 했기에 그것보다 하나 큰 12로 배열 크기를 잡았다.
dp[0]은 0으로 비워두고 dp[1] =1, dp[2] =2, dp[3] = 4가 나온다.
n이 1~3인경우에는 간단한 산수로 구해지는데 dp[4]의 경우에는 여러 경우의 수를 계산하면 7이 나온다.
i>=4에 대해서 다음 점화식이 성립한다.
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
import java.util.*;
public class Main {
static int[] dp = new int[12];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
dp[0] = 0;
dp[1] = 1;
dp[2] = dp[1] * dp[1] + 1;//2
dp[3] = dp[1] * dp[2] + dp[2] * dp[1] + 1 - 1; //4
// dp[4] = 7
//dp[5] = 13
for (int i = 4; i <= 11; i++) {
dp[i] += dp[i - 1] + dp[i - 2] + dp[i - 3];
}
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int num = sc.nextInt();
System.out.println(dp[num]);
}
}
}