백준 1309 : 동물원

1. 문제 : https://www.acmicpc.net/problem/1309

1309번: 동물원

 

2. 문제 접근

• 백트레킹
  • $2N$개의 칸 중 $A$라는 지점에 사자를 배치.
  • 다음 탐색 노드를 선정해야하지만 사자를 배치하는 순서가 없기에 $A$ 지점을 제외한 모든 지점을 탐색해야 함.
  • 즉 자식 노드의 갯수가 $2N$개가 되는 괴랄한 트리를 탐색해야 하기에 사용할 수 없음.
• DP
  • $N = K$일 때 사자를 배치한 경우의 수는 $N = K - 1$일 때 사자를 배치한 경우의 수에 왼쪽 혹은 오른쪽에 사자를 배치하거나 배치하지 않는 경우의 수를 추가하여 구할 수 있음.
  • 이를 점화식으로 만들 수 있으므로 DP 사용 가능.

 

3. 문제 해결

1. $N = 1$일 때 경우의 수를 저장.
2. $N = K$일 때 마지막 줄에 사자를 어떻게 배치하냐에 따라 $N = K + 1$일 때 마지막 줄에 사자를 배치할 수 있는 케이스가 정해짐.
   • $K$번째 줄에 사자를 배치하지 않음 : $K + 1$번째 줄엔 왼쪽 혹은 오른쪽에 사자 배치하거나 배치하지 않음.
   • $K$번째 줄에 사자를 왼쪽에 배치함 : $K + 1$번째 줄엔 오른쪽에 사자를 배치하거나 배치하지 않음.
   • $K$번째 줄에 사자를 오른쪽에 배치함 : $K + 1$번째 줄엔 왼쪽에 사자를 배치하거나 배치하지 않음.
3. $N$까지 계산을 반복한 뒤 세 값을 합해 반환하면 해당 값이 구하고자 하는 값.

// None
DP[K][0] = DP[K - 1][0] + DP[K - 1][1] + DP[k - 1][2];
// Left
DP[K][1] = DP[K - 1][0] + DP[k - 1][2];
// Right
DP[K][2] = DP[K - 1][0] + DP[K - 1][1];

 

 

4. 코드

#include <iostream>
#include <vector>
using namespace std;

int solution(int N)
{
	vector<vector<int>> dp;

	// Initialize the dp array (0 : none, 1 : left, 2 : right)
	dp.push_back({ 1, 1, 1 });
	
	// Calculate the dp array
	for (int i = 1; i < N; i++)
	{
		vector<int> temp;

		// none
		temp.push_back((dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901);
		// left
		temp.push_back((dp[i - 1][0] + dp[i - 1][2]) % 9901);
		// right
		temp.push_back((dp[i - 1][0] + dp[i - 1][1]) % 9901);
		
		dp.push_back(temp);
	}

	return (dp[N - 1][0] + dp[N - 1][1] + dp[N - 1][2]) % 9901;
}

int main()
{
	int N;

	cin >> N;

	cout << solution(N);

	return 0;
}