[백준] 1309번 : 동물원

문제

 

---

풀이

 

dp는 점화식을 세우는게 제일 어렵다...

처음엔 2차원 dp배열을 선언해서 세로가 N(i)일 때 사자 j마리를 넣는다면...식으로 생각했지만,

나눠지는 경우의 수가 너무 많았다.

 

dp인데 경우의 수가 일관적이지 않게 나눠진다면 뭔가 잘못하고 있단 뜻이니 바로 방향을 틀어야 한다...

 

그래서 i번째 줄에 집중하기로 했다. i번째 줄에서 가능한 경우는 3개가 있다.

 

1. 사자가 없다.

2. 왼쪽에 사자가 있다.

3. 오른쪽에 사자가 있다.

 

1번의 경우엔 i-1번째 줄에서 사자가 없든 어디에 있든 상관없다.

2번의 경우엔 i-1번째 줄에서 사자가 없거나 오른쪽에만 있어야 한다.

3번의 경우엔 i-1번째 줄에서 사자가 없거나 왼쪽에만 있어야 한다.

 

정리하자면 dp[100000][3]일 때 dp[i][j]에 대한 점화식은 이렇게 된다.

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

이대로 코드를 짜면된다.

 

점화식 세우는 건 정말 어렵다...

---

소스코드

 

#include <iostream>

using namespace std;

const int DIVISOR = 9901;
int dp[100001][3];

int main() {
    int N;

    cin >> N;
    dp[1][0] = dp[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]) % DIVISOR; //사자가 없다면 이전 행 어디에 사자가 있어도 괜찮음
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % DIVISOR; //사자가 왼쪽에 있다면 이전 행에 사자가 없거나 오른쪽에 있거나
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % DIVISOR; //사자가 오른쪽에 있다면 이전 행에 사자가 없거나 왼쪽에 있거나
    }
    cout << (dp[N][0] + dp[N][1] + dp[N][2]) % DIVISOR;
}