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

예제

코드

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i=0; i<N; i++) {
			int input = Integer.parseInt(br.readLine());
			int dp[] = new int[11];
			
			dp[1] = 1;
			dp[2] = 2;
			dp[3] = 4;
			
			for(int j=4; j<=input; j++)
				dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
			
			System.out.println(dp[input]);
		}
	}
}

풀이

DP (Dynamic Programming)을 이용하여 풀 수 있다.

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]이다.