백준 9095 1, 2, 3 더하기 JAVA (DP)

1. 문제

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

2. 설명

DP로 접근했을 때,

n=4 일 때 경우의 수가

1 + 3 (1의 경우의 수 + 3)

2 + 2 (2의 경우의 수 + 2)

3 + 1 (3의 경우의 수 + 1)

n=5 일 때 경우의 수가

1 + 4 (1의 경우의 수 + 4)

2 + 3 (2의 경우의 수 + 3)

3 + 2 (3의 경우의 수 + 2)

4 + 1 (4의 경우의 수 + 1)

이다.

하지만 1, 2, 3으로만 나타내기 때문에 4를 더하는 경우는 제외해도 됨.

-> n-1, n-2, n-3 까지만 고려하면 된다.

따라서 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

 

3. 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		int[] n = new int[T];
		int[] dp = new int[11];
		
		for(int i=0; i<T; i++) {
			n[i] = scan.nextInt();
		}
		
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		for(int i=0; i<T; i++) {
			for(int j=4; j<=n[i]; j++) {
				dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
			}
			System.out.println(dp[n[i]]);
		}
	}
}