#1309動物園(Zoo)c++

1266 ワード
baekjoon algorithm dynamicprogramming テキストリンク
この問題は前のRGB問題に近似できる.
まず動物園の大きさは横2歳、1歳の場合を考えます.
ライオンが1匹も配置されていない場合は、+左欄+右欄=3種類あります.
次の動物園の大きさを考えると横2歳2歳の場合です.
2行目だけを見ると、1匹のライオンが配置されていない場合は、横2、縦1にライオンが配置されている場合の数の和になります.(2部屋あると思っただけ)
左欄に置く場合は、最初の行にライオンを1匹も置かない+右欄に置く場合と同じです.
右側のバーに配置する場合は、最初の行にライオン+を1匹も置かない場合と同じです.


#include<iostream>

const int MAX = 100001;
const int MOD = 9901;

using namespace std;

int makeDen(int n) {
	
	int dp[MAX][3];

	dp[1][0] = dp[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;
	}

	return (dp[n][0] + dp[n][1] + dp[n][2])%MOD;
}


int main() {
	int n;

	cin >> n;
	if (n > MAX)
		exit(EXIT_FAILURE);

	cout << makeDen(n) << endl;

	return 0;
}
[アルゴリズム]BOJ 2573(氷山)
Bitcoin hash-rateは二次攻撃を予測する