[다이나믹 #3] 백준 9095번: 1, 2, 3더하기 JAVA

9095번: 1, 2, 3 더하기

문제

---

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

 

출력

---

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

 

예제 입력

---

예제 입력	예제 출력
3 4 7 10	7 44 274

 

 

풀이

---

d[0]은 0

d[1] = 1밖에 없으니 경우의 수는 1

d[2] = (1 + 1), (2) 즉 경우의 수는 2

d[3] = (1 + 1 + 1), (1 + 2), (2 + 1), (3) 즉 경우의 수는 3

 

d[4]를 생각할 때

1. 4는 1 + 3 이다. 3을 1, 2, 3 더하기로 하였을 때의 경우의 수는 4가지이다.
2. 4는 2 + 2이다. 2를 1, 2, 3 더하기로 하였을 때의 경우의 수는 2가지이다.
3. 4는 3 + 1이다. 3을 1, 2, 3 더하기로 하였을 때의 경우의 수는 1가지이다.

즉, 4 + 2 + 1을 하면 7가지가 된다.

이렇게 d[5]를 마저 생각하게 되면

1. 5는 1 + 4이다. 4를 1, 2, 3 더하기로 하였을 때의 경우의 수는 7가지이다.
2. 5는 2 + 3이다. 3를 1, 2, 3 더하기로 하였을 때의 경우의 수는 4가지이다.
3. 5는 3 + 2이다. 2을 1, 2, 3 더하기로 하였을 때의 경우의 수는 2가지이다.

즉, 7 + 4 + 2를 하면 d[5]는 13개가 된다.

 

 

 

코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

	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());
		int[] num = new int[t];
		int[] dp = new int[12];
		
		for(int i=0; i<t; i++) {
			num[i] = Integer.parseInt(br.readLine());
		}
		
		dp[1] =1;
		dp[2] = 2;
		dp[3] = 4;
		
		for(int i=4; i<=11; i++) {
			dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
		}
		
		for(int i=0; i<t; i++) {
			bw.write(dp[num[i]]+"\n");
		}
		bw.flush();
		bw.close();
		
	}
}