[백준/C++] 1309번_동물원

문제는 다음과 같습니다.

일단 문제가 너무 귀엽습니다 동물원이라니🐶🙊🐯🐻🐰

일단 저는 바로 N번째 상황에 대해 가정하고 바로 점화식으로 접근하였습니다.

N번째 상황에서 경우의 수는 3가지입니다.

1. 앞의 두 칸이 모두 비어있는 경우
2. 앞에서 왼쪽만 차있는 경우
3. 앞에서 오른쪽만 차있는 경우

그리고 각각의 경우에 대해서 식을 세웠습니다.

2차원 배열을 이용하였고,

dp[N][i]에 대해서, N은 N번째 행을 의미합니다

• N번째 행에서 모두 비어있는 경우를 dp[N][0]
• N번째 행에서 왼쪽만 차있는 경우를 dp[N][1]
• N번째 행에서 오른쪽만 차있는 경우를 dp[N][2]

라고 설정했습니다.

그리고 각각의 경우에 대해서 점화식은 다음과 같습니다.
❗️문제조건: 가로로도 세로로도 붙어 있게 배치할 수 없음

• dp[N][0] = dp[N-1][0]+dp[N-1][1]+dp[N-1][2]
• dp[N][1] = dp[N-1][0]+dp[N-1][2]
• dp[N][2] = dp[N-1][0]+dp[N-1][1]

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

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

    long long dp[100001][3]={0, };
    long long mod = 9901;
    int n; cin>>n;

    for(int i=0; i<=2; i++) dp[0][i]=1;

    for(int i=1; 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;
    }

    long long res = 0;
    for(int i=0; i<=2; i++) res+=dp[n-1][i];
    cout<<res%mod<<"\n";
    return 0;
}