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

[알고리즘 분류]
다이나믹 프로그래밍

 

풀이

정수 1, 2, 3을 문제의 규칙대로 나누면 다음과 같다.

 

1 - 1 : 1개

2 - 1 + 1, 2 : 2개

3 - 1 + 1 + 1, 1 + 2, 2 + 1, 3 : 4개

 

입력 받은 정수 n을 1, 2, 3의 케이스로 쪼개서 방법 수의 합을 구하면 된다.

#include <stdio.h>

int dp(int n)
{
	if (n == 0)
		return 0;
	else if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else if (n == 3)
		return 4;

	return dp(n - 1) + dp(n - 2) + dp(n - 3);
}

int main(void)
{
	int T, n;

	scanf("%d", &T);
	for (int i = 0; i < T; i++)
	{
		scanf("%d", &n);
		printf("%d\n", dp(n));
	}

	return 0;
}

 

여담

각 방법마다 어떻게 더해지는지 확인해보려고 했는데 바보같은 짓이었다.

 

출처

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