[DP] 백준 1309번 동물원(C++)

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

 

동물원 좋아요

정말좋아요

 

문제 이해는 어렵지 않을거라 본다

 

우리는 정말 수많은 DP문제들을 풀어보았다.. 그렇지않은가?

 

그럼 감이 올 것이다.

 

저 2칸에 대해서 나올 수 있는 경우의 수는 3가지

 

왼쪽에만 없거나

오른쪽에만 없거나

둘다 없거나..

 

그래서 ..

 

dp[i]번째에 대해서 dp[i-1]번째에 대한 것들을 더할때,

 

dp[i][왼쪽] = dp[i-1]][오른쪽[+dp[i-1][둘다없을때]

를 하면된다...

#include <iostream>

#include <cmath>

using namespace std;

long dp[100001][3];

long MOD = 9901;

int main()

{

    int n;

    cin >> n;

    dp[1][0] = 1; // 왼쪽

    dp[1][1] = 1; // 오른쪽

    dp[1][2] = 1; // 아무것도 ㄴㄴ

    for (int i = 2; i < 100001; i++)

    {

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

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

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

        dp[i][0] %= MOD;

        dp[i][1] %= MOD;

        dp[i][2] %= MOD;

    }

    long sum;

    sum = dp[n][0] + dp[n][1] + dp[n][2];

    sum %= MOD;

    cout << sum << "\n";

}

흐으