[백준,c++] 1309번 - 동물원

문제

1309번: 동물원

코드

#include <iostream>
#define MOD 9901
using namespace std;

int dp[100001][3];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    dp[0][0] = 1;   // 사자를 놓지않는 경우
    dp[0][1] = 1;   // 사자를 왼쪽에 배치하는 경우
    dp[0][2] = 1;   // 사자를 오른쪽에 배치하는 경우z
    
    int N; cin>>N;
    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;
    }
    cout<<(dp[N-1][0] + dp[N-1][1] + dp[N-1][2]) % MOD;
}

풀이

DP문제입니다. 코드의 주석에도 적혀 있듯이, 배열을 아래와 같이 설정합니다.

• dp[index][0]: 해당 칸에 사자를 놓지 않을때 지금까지 선택 할 수 있는 총 경우의 수
• dp[index][1]: 해당 칸의 왼쪽에 사자를 놓았을때 지금까지 선택 할 수 있는 총 경우의 수
• dp[index][2]: 해당 칸의 오른쪽에 사자를 놓았을때 지금까지 선택 할 수 있는 총 경우의 수

그 뒤, 아래와 같이 반복문을 돌려 계산합니다.

• 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;
  
  • 현재칸의 오른쪽에 사자를 놓는 총 경우의 수 = (이전칸에 사자를 놓지 않는 총 경우의 수 + 이전칸의 왼쪽에 사자를 놓는 총 경우의 수)

그 뒤, 총 경우의 수 = (현재 칸에 사자를 놓지 않는 경우 + 현재 칸의 왼쪽에 사자를 놓는 경우 + 현재의 오른쪽에 사자를 놓는 경우)를 출력합니다.