백준 1309번 동물원 C++

출처 : https://www.acmicpc.net/problem/1309

 

다이나믹 프로그래밍으로 해결할 수 있는 문제이다.

3가지 경우가 있는데, 사자를 배치하지 않는 경우, 왼쪽에 배치하는 경우, 오른쪽에 배치하는 경우가 있다.

dp[n][3] 의 dp테이블을 만들어서

0열에는 배치하지 않을 때의 경우의 수,

1열에는 왼쪽에 배치할 때의 경우의 수, 

2열에는 오른쪽에 배치할 때의 경우의 수를 넣어서 문제를 해결할 수 있다.

우선 우리의 크기가 1일 때에는 dp[1][0] = 1, dp[1][1] = 1, dp[1][2] =1 로 모두 하나의 경우의 수를 가진다.

다음 우리의 크기가 2일 때에는 

사자를 배치하지 않는 경우는 위의 세 가지 경우 모두 가능하기 때문에 dp[2][0]=dp[1][0]+dp[1][1]+dp[1][2] 이다.

사자를 왼쪽에 배치하는 경우는 1행에서 사자를 배치하지 않는 경우와 사자를 오른쪽에 배치하는 경우에만 가능하기 때문에 dp[2][1] = dp[1][0] + dp[1][2] 이다.

사자를 오른쪽에 배치하는 경우는 1행에서 사자를 배치하지 않는 경우와 사자를 왼쪽에 배치하는 경우에만 가능하기 때문에 dp[2][2] = dp[1][0] + dp[1][1] 이다.

 

여기에서 얻을 수 있는 점화식은

dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]
dp[i][1] = dp[i - 1][0] + dp[i - 1][2]
dp[i][2] = dp[i - 1][0] + dp[i - 1][1]

 

이다.

 

총 경우의 수는 dp[n][0] + dp[n][1] + dp[n][2]를 해주면 된다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>

using namespace std;
typedef long long ll;

const int mod = 9901;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	if (n == 1) {
		cout << 3;
		return 0;
	}
	vector<vector<int>> dp(n + 1, vector<int>(3, 0));
	//0 : 배치x, 1: 왼쪽, 2: 오른쪽
	dp[1][0] = 1;
	dp[1][1] = 1;
	dp[1][2] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
		dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
	}
	int ans = (dp[n][0] + dp[n][1] + dp[n][2]) % mod;
	cout << ans;
};