[백준 C++] 1309번: 동물원

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

 

이 문제만 풀고 자자

 

dp 예제이다. 2 * n 표에 사자를 배열하면 되는데 가로든 세로든 겹쳐서는 안되는 모양이다. 사자가 없는 경우도 하나의 경우의 수로 생각한다.

 

n = 1일때 한마리를 양쪽에 넣는 경우밬에 없으므로 2이다. + 1 아무도 없는 경우 3

 

n = 2 일때 한마리를 놓는 경우는 4이고 두마리를 넣는 경우는 2이므로 6이다. + 1 아무도 없는 경우 7

 

n = 3 일때 한마리를 놓는 경우는 6이고 두마리를 넣는 경우는 8 세마리를 넣는 경우는 2 16이다. + 1 아무도 없는 경우 17

 

n = 4 일때 한마리를 놓는 경우는 8이고 두마리를 넣는 경우는 5 + 5 + 3 + 3 + 1 + 1 18, 세마리를 넣는 경우는 3 + 3 + 1 + 1 + 1 + 1 10, 네마리를 넣는 경우는 2 총 38 세가지 경우는 어디갔지,,, 일단 우리의 사자가 한마리도 없는 경우 +1 해도 두가지 경우가 남는데 세는것을 잊은 것같다. 

 

계산해보면서 느낀것은 우선 배열을 삼차원 배열로 설정해서 따로 계산해 준뒤 합쳐주어야 할꺼같다. 왜냐하면

 

 

우리에 몇마리가 들어가는것이 중요한게 아니다. 이전에 넣은 사자 중 맨 밑에 칸에 사자가 어디에 위치해있나가 중요하다. 사자가 한마리도 없는경우를 dp[i][0]에 저장하고 왼쪽에 있는 경우dp[i][1], 오른쪽에 있는 경우 dp[i][2]에 저장해준다. dp[i+1][0]값은 안들어갈수도 있고 왼쪽에 들어갈 수도 있고 오른쪽에 들어갈 수도 있다. 따라서 dp[i+1][0] = dp[i][0] + [dp[i][1] + dp[i][2]이다. dp[i+1][1]값은 dp[i][0] + dp[i][2]값이고 dp[i+1][2]값은 dp[i][0] + dp[i][1]이다.

 

n = 1일때 dp[1][0] = 1, dp[1][1] = 1, dp[1][2] = 1

n = 2 일때 dp[2][0] = 3, dp[2][1] = 2, dp[2][2] = 2 총 7이다.

n = 3 일때 7, 5, 5 총 17

n = 4 일때 17 12 12 총 41 예제와 일치한다.

 

이와같이 코드를 짜보면

 

#include <iostream>
#include <algorithm>
#define MAX 100001
#define MODULER 9901
using namespace std;
long long dp[MAX][3] = { 0, };
 
int main(int argc, char* argv[])
{
    int n;
    cin >> n;
    dp[0][0] = 1;
    dp[0][1] = 1;
    dp[0][2] = 1;
    for (int i = 1;i < n;i++) {
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MODULER;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MODULER;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MODULER;
    }
 
    cout << (dp[n - 1][0] + dp[n - 1][1]  + dp[n - 1][2]) % MODULER << '\n';
 
    return 0;
}

 

나누어주는거 이번엔 안잊었다.