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

 

풀이

---

F(N) = F(N-1) + F(N-2) + F(N-3)

해당 문제는 위 식으로 문제를 풀 수 있다.

 

경우의 수를 나열하면 이유를 알 수 있다.

정수	경우의 수
1	1 = (1개)
2	1+1, 2 (2개)
3	1+1+1, 1+2, 2+1 (3개)
4	1+... , 2+... , 3+...  (7개)
5	...(12개)

여기서 1+ 와 2+, 3+들은 고정된 것이라고 보면 규칙이 보인다.

 

4를 예로 들어 보자.

4를 1,2,3 으로 표현하는 방법은 1+3, 2+2, 3+1로 나눌 수 있다.

 

1+ 로 표현할 수 있는 4의 경우의 수는 몇 개일까?

이때, 1+는 고정된 값으로 생각하면

3을 표현할 수 있는 경우의 수만큼 의 경우의 수가 나온다.

 

4=2+2 일 경우에는 2+(2의 경우의 수) 만큼의 경우의 수가 나오게 된다.

4=3+1 의 경우도 같은 방식이다.

 

 

이를 코드로 표현해 보자.

 

최종 코드

#include <stdio.h>
int main(void) {
	int dp[12];

	int T;
	scanf("%d", &T);
	
	int n;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	
	for(int i = 0; i < T; i++){
		scanf("%d", &n);
		for(int j = 4; j <= n; j++){
			dp[j] = dp[j-3] + dp[j-2] + dp[j-1];
		}
		printf("%d\n", dp[n]);
	}
	
	return 0;
}