[백준][C++] 9095번 문제 "1, 2, 3 더하기" (다이나믹 프로그래밍, 백트래킹)

출처: 백준

9095번 문제

문제

---

본문

---

정수 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

---

3
4
7
10

예제 출력 1

---

7
44
274

문제 해석

---

  문제는 단순합니다. 주어지는 숫자 n을 1, 2, 3의 조합으로 표현하면 됩니다.

해결방법

---

  두가지 방법으로 풀 수 있는데 한가지는 다이나믹 프로그래밍으로 해결하는 방법과 백트래킹을 사용하면 됩니다.

1. 다이나믹 프로그래밍

  문제를 보면 간단한 규칙 한가지를 발견할 수 있습니다. 일단 n이 1, 2, 3일 경우를 먼저 구합니다. 이를 case(1), case(2), case(3)이라고 하겠습니다. 그 결과는 다음과 같습니다.

Case(1)	Case(2)	Case(3)
1	2 1 + 1	3 1 + 2 2 + 1 1 + 1 + 1

  이제 n = 4일 경우를 생각해봅시다. Case(4)는 다음과 같이 나타낼 수 있습니다.

3 + Case(1)	2 + Case(2)	1 + Case(3)
3 + 1	2 + 2 2 + 1 + 1	1 + 3 1 + 1 + 2 1 + 2 + 1 1 + 1 + 1 + 1

즉 Case(4) = Case(1) + Case(2) + Case(3) 인 것을 알 수 있습니다.

1. 백트래킹

  루트 노드를 1로 잡고 백트래킹을 활용하여 푸는 방법도 있습니다.

Code

1. 다이나믹 프로그래밍

#include <iostream>

using namespace std;

int	test_case, n, arr[11];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	arr[0] = 0;
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;
	for (int arr_index = 4; arr_index < 11; arr_index++)
		arr[arr_index] = arr[arr_index - 1] + arr[arr_index - 2] + arr[arr_index - 3];

	cin >> test_case;

	while(test_case)
	{
		cin >> n;
		cout << arr[n] << '\n';
		test_case--;
	}

	return (0);
}

1. 백트래킹

#include <iostream>

using namespace std;

int	test_case, n, sum_case, arr[10];

int	sumAll(void)
{
	int sum = 0;

	for (int arr_index = 0; arr[arr_index]; arr_index++)
		sum += arr[arr_index];
	return (sum);
}

void	backtracking(int curr)
{
	if (sumAll() == n)
	{
		sum_case++;
		return ;
	}

	for (int num = 1; num <= 3; num++)
	{
		arr[curr] = num;
		if (sumAll() <= n)
		{
			backtracking(curr + 1);
			arr[curr] = 0;
		}
		else
		{
			arr[curr] = 0;
			return ;
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> test_case;

	while(test_case)
	{
		cin >> n;
		sum_case = 0;
		backtracking(0);
		cout << sum_case << '\n';
		test_case--;
	}

	return (0);
}

Reference