[백준][JAVA] 9095번 : 1, 2, 3 더하기 ( *DP )

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

9095번: 1, 2, 3 더하기

---

이 문제는 다이나믹 프로그래밍을 이용하여 풀 수 있다.

dp 1차원 배열을 생성하고, dp[n] 는 정수 n을 1,2,3 의 합으로 나타낼 수 있는 경우의 수를 의미한다.

 

dp[1] 은 1로만 나타낼 수 있으므로 1가지이다.

 

n = 1 일 때,

1

한 가지이므로 dp[1] = 1 이다.

 

n = 2 일 때,

1 + 1

2

두 가지이므로 dp[2] = 2 이다.

 

n = 3 일 때,

1 + 1 + 1

2 + 1

1 + 2

3

총 4가지이므로 dp[3] = 4 이다.

 

n = 4 일 때,

1 + 1 + 1 +1

2 + 1 + 1

1 + 2 + 1

3 + 1

1 + 1 + 2

2 + 2

1 + 3

총 7가지이므로 dp[4] = 7 이다.

그런데 n = 4 인 경우의 수에서 아래의 빨간색 부분의 연산은 dp[3]에 포함된 경우의 수와 같다.

1 + 1 + 1 +1

2 + 1 + 1

1 + 2 + 1

3 + 1

 

아래의 파란색 부분의 연산 역시 dp[2]에 포함된 경우의 수와 동일하다.

1 + 1 + 2

2 + 2

 

아래의 초록색 부분의 연산은 dp[1]에 포함된 경우의 수이다.

1 + 3

 

즉, dp[4] 는 결국 dp[3] + dp[2] + dp[1]을 더한 것과 같다.여기서 얻을 수 있는 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-1] 이 된다.점화식을 얻었으니 이를 이용하여 dp의 값들을 구할 수 있다.

 

 

import java.util.*;
import java.math.*;
public class Main {
	
	static int dp[] = new int [11];
	
	public static void main(String[] args)   {
		Scanner kb = new Scanner(System.in);
		
		int t = kb.nextInt();
		dp[1]=1; //초기 값 초기화
		dp[2]=2;
		dp[3]=4;
		
		for(int j=4;j<=10;j++) { // 4부터 반복
			dp[j] = dp[j-3] + dp[j-2] + dp[j-1]; // 점화식
		}
		
		for(int i=0;i<t;i++) {
			int n = kb.nextInt();
			System.out.println(dp[n]);
		}
	}
}