[백준 1309] 동물원 C++

1309번: 동물원

다이나믹 프로그래밍 기초

---

1. 문제풀이 아이디어

row행에서 사자를 놓는 모든 경우의 수 = row행에 사자를 놓지 않는 경우 + row행의 1번에만 사자를 놓는 경우 + row행의 2번에만 사자를 놓는 경우

row행에 사자를 놓지 않는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 1번에만 사자를 놓는 경우 + row+1행의 2번에만 사자를 놓는 경우

row행의 1번에만 사자를 놓는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 2번에만 사자를 놓는 경우

row행의 2번에만 사자를 놓는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 1번에만 사자를 놓는 경우

row가 5일때 dp table

---

2. 코드

탑 다운 방식과 바텀 업 방식을 모두 사용해보았다

#include <iostream>
#include <cstring>
 
using namespace std;
 
int N, dp[100001][3];
 
int top_down(int row, int cage){
    
    if(row == N-1) return 1;
    
    int &ret = dp[row][cage];
    if(ret != -1) return ret;
    
    ret = 0;
    
    switch(cage){
        case 0:
        ret += (top_down(row+1, 0) + top_down(row+1, 1) + top_down(row+1, 2))%9901;
        break;
        
        case 1:
        ret += (top_down(row+1, 0) + top_down(row+1, 2))%9901;
        break;
        
        case 2:
        ret += (top_down(row+1, 0) + top_down(row+1, 1))%9901;
        break;
        
        default: break;
    }
    
    return ret % 9901;
}
 
void bottom_up(){
    dp[1][0] = 1;
    dp[1][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])%9901;
        dp[i][1] = (dp[i-1][0] + dp[i-1][2])%9901;
        dp[i][2] = (dp[i-1][0] + dp[i-1][1])%9901;
    }
    cout << (dp[N][0] + dp[N][1] + dp[N][2])%9901;
}
 
int main(){
    cin >> N;
    // memset(dp, -1, sizeof(dp));
    // cout << (top_down(0, 0) + top_down(0, 1) + top_down(0, 2))%9901;
    bottom_up();
    
    return 0;
}