백준 1309번 동물원 - C++ 풀이

---

 

1. dp(idx, prev) : (idx-1) 번째 행의 상태가 prev일 때 idx번 행~마지막까지 채우는 방법의 수
2. prev = 0 이면, dp(idx, prev) = dp(idx+1, 0) + dp(idx+1, 1) + dp(idx+1, 2)
3. prev > 0 이면, dp(idx, prev) = dp(idx+1, 0) + dp(idx+1, 3-prev)

 

1. dp(idx, prev) : (idx-1)번째 행의 상태가 prev일 때 idx번 행~마지막까지 채우는 방법의 수

 dp(idx, prev)를 위와 같이 정의하자. 사자가 세로로 붙어있을 수 없으므로 prev값이 필요하다. 이때 사자가 가로로 붙어있을 수 없으므로 한 행 내의 사자 상태는 아예 없거나, 오른쪽 칸에만 있거나, 왼쪽 칸에만 있어야 한다. 아래 코드에서는 각 상태를 0, 1, 2로 정의하고 풀이하였다.

 

2. prev = 0 이면, dp(idx, prev) = dp(idx+1, 0) + dp(idx+1, 1) + dp(idx+1, 2)

 이전 행에 사자가 없었으면, 즉 prev = 0 인 경우, 현재 행에는 사자를 배치하는 모든 경우가 가능하다.

 

3. prev > 0 이면, dp(idx, prev) = dp(idx+1, 0) + dp(idx+1, 3-prev)

 이전 행에 사자가 있었으면, 현재 행에는 아예 배치하지 않거나 대각선으로 배치해야 한다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;
const int MOD = 9901;

int N;
int cache[100001][3];

int dp(int idx, int prev) {
    if (idx == N) return 1;
    
    int& ret = cache[idx][prev];
    if (ret != -1) return ret;
    
    ret = dp(idx+1, 0);
    if (prev != 2) ret = (ret + dp(idx+1, 2)) % MOD;
    if (prev != 1) ret = (ret + dp(idx+1, 1)) % MOD;
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    
    cin >> N;
    cout << dp(0, 0);

    return 0;
}