9095 1, 2, 3 더하기

 

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