[Java] 백준(Baekjoon) 9095. 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

 

 

 

---

 

풀이

1. 1 을 나타내는 방법

-> 1

 

1-2. 2를 나타내는 방법 -> 2

- 2

- 1+1

 

1-3. 3을 나타내는 방법 -> 4

- 3

- 1+2

- 2+1

- 1+1+1

 

2. 4를 나타내는 방법

- 1+1+1+1 

- 1+1+2

- 1+2+1

- 2+1+1

- 2+2

- 1+3

- 3+1

-> 7개

 

3. 5를 나타내는 방법

- 1+1+1+1+1

- 1+1+1+2(4개)

- 1+1+3(3개)

- 2+2+1(3개)

- 2+3(2개)

-> 13개

 

4. 6을 나타내는 방법

- 1+1+1+1+1+1

- 1+1+1+1+2(5개)

- 1+1+1+3(4개)

- 1+2+3(6개) 3 2 1    1 3 2    2 3 1   등

- 1+1+2+2(6개)

- 2+2+2

- 3+3

-> 24개

 

5. 7을 나타내는 방법

- 1+1+1+1+1+1+1

- 1+1+1+1+1+2(6개)

- 1+1+1+1+3(5개)

- 1+1+1+2+2(10개)

- 1+1+2+3(12개)

- 1+3+3(3개)

- 2+2+3(3개)

=> 40

44?

 

1 2 4 7 13 24 44

 

dp [n] = dp [n-1] + dp [n-2] + dp [n-3]

 

package dp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Ex9095 {
	
	static int dp[] = new int[11]; //n<11

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		dp[1]=1;
		dp[2]=2;
		dp[3]=4;
		
		for(int j=4;j<11;j++) {
			dp[j]=dp[j-1]+dp[j-2]+dp[j-3];
		}
		
		int row = Integer.parseInt(br.readLine());
		
		for(int i=0; i<row; i++) {
			int num = Integer.parseInt(br.readLine());
			
			System.out.println(dp[num]);
			
		}
	}

}