이것 저것 &

문제링크:https://www.acmicpc.net/problem/1309

dp문제입니다!

n일때의 경우의수는 n-1일때와 관계가 있습니다.

n번째 줄에 사자가 없을때 왼쪽에 있을때 오른쪽에 있을때 이렇게 3가지로 나눠보겠습니다. 

0인덱스가 사자가 없을때 1인덱스가 왼쪽에 있을때 2인덱스가 오른쪽에 있을때 입니다.

1. n번째 줄에 사자가 없을때

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

2. n번째 줄에 왼쪽에 사자가 있을때

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

3. n번째 줄에 오른쪽에 사자가 있을때

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

9901로 계속 나눠주면서 결과를 도출하는 것도 잊으시면 안됩니다. 

증가하는 규칙을 찾으면 정말 쉬운 문제였습니다.

정답코드입니다.

#include <iostream>
using namespace std;
int dp[100001][3] = { 0 };
int n = 0;
int main() {
	cin >> n;
	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];
		dp[i][1] = dp[i - 1][0] + dp[i - 1][2];
		dp[i][2] = dp[i - 1][0] + dp[i - 1][1];

		dp[i][0] %= 9901;
		dp[i][1] %= 9901;
		dp[i][2] %= 9901;
	}

	cout << (dp[n][0] + dp[n][1] + dp[n][2]) % 9901 << endl;

}