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

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

9095번: 1, 2, 3 더하기

---

문제

 

 

풀이

가능한 연산은 1을 더하기, 2를 더하기, 3을 더하기 3가지입니다.

1은 [1] 로 1가지, 2는 [1+1, 2]로 2가지, 3은 [1+1+1, 2+1, 1+2, 3]으로 4가지, ... 등으로 나올 것입니다.

 

dp 테이블에는 i를 1, 2, 3을 더하여 만들 수 있는 경우의 수가 들어갈 것입니다.

i를 만들기 위해서는 i-1에 1을 더하기, i-2에 2를 더하기, i-3에 3을 더하기 3가지 경우가 있습니다. 따라서 dp[i]는 3가지 경우를 모두 합한 값이 될 것입니다. 이를 점화식으로 나타내면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]이 됩니다.

 

예를 들어보면 4의 경우에는 1) 3에 1 더하기, 2) 2에 2 더하기, 3) 1에 3 더하기 이기 때문에 

1	2	3
1	1+1 2	1+1+1 2+1 1+2 3

 

1) 3에 1 더하기는 다음과 같이 3의 경우에 1을 더하는 경우인 4가지입니다.

• 1+1+1+1
• 2+1+1
• 1+2+1
• 3+1

 

2) 2에 2 더하기는 다음과 같이 2의 경우에 2를 더하는 경우인 2가지입니다.

• 1+1+2
• 2+2

 

3) 1에 3 더하기도 다음과 같이 1의 경우에 3을 더하는 경우인 1가지입니다.

• 1+3

 

따라서 4는 총 7가지가 나옵니다.

 

 

소스코드

• n은 11보다 작기 때문에 dp 테이블은 0부터 10까지 나타내므로 길이는 11입니다.

import java.util.*;
import java.io.*;

public class BJ9095 {
	
	// n < 11 (0 ~ 10)
	static int[] dp = new int[11];

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t=0; t<T; t++) {
			int n = Integer.parseInt(br.readLine());
			
			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];
			}
			
			System.out.println(dp[n]);
		}
	}

}