1, 2, 3 더하기 (백준 - 9095번)

동적계획법을 사용하는 문제이다.

 

규칙을 먼저 살펴보자.

 

* 1일 경우

1

-> 1개

 

* 2일 경우

1 + 1

2

-> 2개

 

* 3일 경우

1 + 1 + 1

2 + 1

1 + 2

3

-> 4개

 

* 4일 경우

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

2 + 1 + 1

2 + 1

1 + 3

3 + 1

-> 7개 (혹은 F(3) + F(2) + F(1) = 4 + 2 + 1 = 7)

 

* 5일 경우

1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1

1 + 2 + 1 + 1

1 + 1 + 2 + 1

1 + 1 + 1 + 2

2 + 2 + 1

2 + 1 + 2

1 + 2 + 2

3 + 1 + 1

1 + 3 + 1

1 + 1 + 3

2 + 3

3 + 2

-> 13개 (혹은 F(4) + F(3) + F(2) = 7 + 4 + 2 = 13)

 

F(N) = F(N - 1) + F(N - 2) + F(N - 3)라는 규칙이 나왔다.

이 규칙을 이용하여 DP 배열을 만들어 N의 최대 갯수인 11 인덱스 위치까지 분기문으로 연산을 한 후에 각 테스트 케이스의 값을 인덱스 위치로 하여 값을 출력해주면 된다.

 

규칙 특성상 DP 배열의 인덱스 4부터 시작해야 하므로 0, 1, 2, 3 인덱스는 값을 각각 0, 1, 2, 4로 정해준다.

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

int main()
{
	int dp[12];

	dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 4;
	for (int i = 4; i <= 11; ++i)
	{
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
	}

	int input;
	cin >> input;

	int* test_case = new int[input];
	for (int i = 0; i < input; ++i)
	{
		cin >> test_case[i];
	}

	for (int i = 0; i < input; ++i)
	{
		cout << dp[test_case[i]] << endl;
	}

	delete[] test_case;
}