1309 : 동물원(Bottom-Up, Top-Down)

https://www.acmicpc.net/problem/1309

1309번: 동물원

 

 

이번 문제는, 점화식을 생각해서 잘 풀었다.

 

 

---

 

 

DP[N]을 세로 길이가 2 * N인 우리에 사자를 놓는 방법이라고 가정하자.

 

 

 

DP[N - 1]을 이용해서, DP[N]을 구할 수 있을까?

 

 

 

DP[N - 1]의 마지막 우리에 사자가 좌, 우 혹은 없음에 따라서, DP[N]에 나올 수 있는 값이 달라진다.

 

 

 

따라서, DP에 마지막 우리에 사자의 좌, 우 혹은 없음을 표시해줘야 한다.

 

 

 

0 - 사자가 좌

1 - 사자가 우

2 - 사자가 없음

 

 

 

이라고 했을 때, DP를 세워보자.

 

 

 

 

DP[0][N] = DP[1][N - 1] + DP[2][N - 1];

 

 

 

 

N에서 마지막 우리에 사자가 좌에 있을 때는, N - 1에서 사자가 우에 있을 때 N에 사자의 좌에 배치할 수 있고, N - 1에서 사자가 없을 때, N에 사자를 좌에 배치할 수 있다.

 

 

 

 

위의 방식으로, 1 , 2의 상태일 떄도 구해주면 된다.

 

 

 

---

 

 

 

해설코드(C++).

 

- Bottom-Up

 

#include <iostream>
 
using namespace std;
 
long long dp[3][100001];
long long result;
int N;
int main(void) {
    cin >> N;
    dp[0][1] = 1;
    dp[1][1] = 1;
    dp[2][1] = 1;
    for (int i = 2; i <= N; i++) {
        dp[0][i] = ((dp[2][i - 1] % 9901) + (dp[1][i - 1] % 9901) % 9901);
        dp[1][i] = ((dp[1][i - 1] % 9901) + (dp[0][i - 1] % 9901) + (dp[2][i - 1] % 9901) % 9901);
        dp[2][i] = ((dp[0][i - 1] % 9901)+ (dp[1][i - 1] % 9901) % 9901);
    }
 
    cout << (dp[0][N] + dp[1][N] + dp[2][N]) % 9901 << endl;
    return 0;
}

 

 

 

- Top-Down

 

 

#include <iostream>
#include <cstring>
 
using namespace std;
 
long long dp[3][100001];
long long result;
int N;
 
long long solve(int status, int N) {
    if (dp[status][N] != -1)
        return dp[status][N];
 
    if (N == 1)
        return 1;
    
    dp[status][N] = 0;
    if (status == 0) {
        dp[status][N] += (solve(2, N - 1) % 9901 + solve(1, N - 1) % 9901);
    }
    else if (status == 1) {
        dp[status][N] += (solve(0, N - 1) % 9901 + solve(1, N - 1) % 9901 + solve(2,  N- 1) % 9901);
    }
    else {
        dp[status][N] += (solve(0, N - 1) % 9901) + (solve(1, N - 1) % 9901);
    }
 
    return dp[status][N] % 9901;
}
int main(void) {
    cin >> N;
    memset(dp, -1, sizeof(dp));
    
    cout << (solve(0, N) + solve(1, N) + solve(2, N)) % 9901 << endl;
    return 0;
}