풀이)
11보다 작은 자연수 N에 대하여, 1, 2, 3의 합으로 나타낼 수 있는 가짓수를 구하여라. 단, 1+2와 2+1은 다른 것으로 치부한다.
다이나믹 프로그래밍 방식으로 풀어야 한다.
DP란 일반적인 재귀에서 더 나아가, 이전 재귀 계산 값을 저장하고 그 다음 재귀에서 계산 값을 활용하는 방식이다.
해당 문제는 'N=4일 때' = 'N=3일 때'+'N=2일 때'+'N=1일 때' 이므로 DP를 이용해 해결한다.
내 코드)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Backjoon9095 {
public static void main(String[]args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
StringBuilder sb = new StringBuilder();
int[] dp = new int[11];
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for(int i=4;i<=10;i++) {
dp[i] = dp[i-1] + + dp[i - 2] + dp[i - 3];
}
for(int t=0;t<T;t++) {
int N = Integer.parseInt(bf.readLine());
sb.append(dp[N]);
sb.append("\n");
}
System.out.println(sb);
}
}