[백준]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의 합으로 나타내는 방법의 수를 출력한다.

 

 

 

---

 

 

 

/* 풀이방법 */

전형적인 DP문제로, 메모이제이션 기법을 사용해서 풀었다.

d[1] = { 1 } = 1가지

d[2] = { 1+1 , 2 } = 2가지

d[3] = { 1+1+1 , 1+2 , 2+1 , 3 } = 4가지

위에 문제를 보면 d[4] = 7가지 임을 알 수있다. 이를 미루어 보아 

d[n] = d[n] + d[n-1] + d[n-2]

이러한 점화식을 세울 수 있다.

                         

 

---

 

/* 해답코드 */

package baekjoon;

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

//dp의 시작
//1,2,3더하기
public class b9095 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		int[] d = new int[11];
		for(int i=0;i<T;i++) {
			int n = Integer.parseInt(br.readLine());
			
			//d[n] = d[n-2]+d[n-1]+d[n]
			d[1]=1;
			d[2]=2;
			d[3]=4;
			for(int j=4;j<=n;j++) {
				d[j] = d[j-1]+d[j-2]+d[j-3];
			}
			System.out.println(d[n]);
		}
	}
}