<Baekjoon>#1309 동물원 (Zoo) c++
이 문제는 앞에서 풀었던 RGB문제와 흡사하게 풀 수 있다.
먼저 동물원의 크기가 가로2 세로1인 경우를 생각해본다.
사자를 한 마리도 배치하지 않는 경우 + 왼쪽 우리에 배치하는 경우 + 오른쪽 우리에 배치하는 경우= 총 3가지가 있다.
다음 동물원의 크기가 가로2 세로2인 경우를 생각해본다.
두 번째 행만 봤을 때 사자를 한 마리도 배치하지 않는 경우는 가로2, 세로1일 때 사자를 배치하는 경우의 수의 합과 같다. (단지 우리 2칸이 생겼다고 생각한다)
왼쪽 우리에 배치하는 경우는 첫 번째 행에서 사자를 한 마리도 배치하지 않는 경우 + 오른쪽 우리에 배치하는 경우의 합과 같다.
오른쪽 우리에 배치하는 경우는 첫 번째 행에서 사자를 한 마리도 배치하지 않는 경우 + 왼쪽 우리에 배치하는 경우의 합과 같다.
#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;
}
Author And Source
이 문제에 관하여(<Baekjoon>#1309 동물원 (Zoo) c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon1309-동물원-Zoo-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)