[BOJ/백준] 1309번 : 동물원 (C++)

[BOJ/백준] 1309번 : 동물원

BOJ 1309

문제 해석

• 2xN인 2차원 배열에서 한 행에는 최대 1마리의 사자를 배치할 수 있다.
• 첫 번째 행에 사자를 배치하는 경우를 제외하면, 각 행에서의 배치는 이전 행에 사자가 있는지 여부에 따라 경우의 수가 달라진다.

풀이

• 첫 번째 행에 사자가 두 위치 중 한 곳에 배치되어 있다면, 다음 행에서는 사자가 대각선 위치에만 배치될 수 있다. 또한, 첫 번째 행에 사자가 존재하면서 두 번째 행에 사자가 배치되지 않는 경우도 가능하다. 세 번째 행의 경우, 두 번째 행에 사자가 존재하느냐 존재하지 않느냐에 따라 배치 방식이 달라진다.

• 즉, k번째 행에 사자가 존재하는 경우는 다음 두 가지에 영향을 받는다.
  • k-1번째 행에 사자가 존재하는 경우
  • k-1번째 행에 사자가 존재하지 않는 경우
  • k번째 행에 사자가 존재하지 않는 경우도 마찬가지이다.
• k번째 행에 사자가 존재하는 경우 다음과 같이 계산할 수 있다.
  • k-1번째 행에 사자가 존재하지 않는 경우, k번째 행에서는 사자를 왼쪽 또는 오른쪽에 배치할 수 있으므로 경우의 수는 DP[k-1][0] X 2
  • k-1번째 행에 사자가 존재하는 경우, k번재 행에서는 대각선 위치에만 배치할 수 있으므로 경우의 수는 DP[k-1][1] X 1이다.
  • 이를 더하면 DP[k][1] = DP[k-1][0] x 2 + DP[k-1][1]이 된다.
• k번째 행에 사자가 존재하지 않는 경우는 k-1번째 행에 사자가 존재하든 존재하지 않든 상관없이 경우의 수가 단순히 두 경우를 더한 값이다.
  • DP[k][0] = DP[k-1][0] + DP[k-1][1]
• 최종 경우의 수는 DP[k][0]+DP[k][1]이다.

코드

#include <iostream>
#include <vector>
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N;//사자 우리의 크기

    vector<vector<int> > DP(N+1,vector<int> (2));

    DP[0][0]=DP[0][1]=0;
    DP[1][0]=1;
    DP[1][1]=2;

    int result;

    for(int i=2; i<N+1; i++){
        DP[i][0]=(DP[i-1][0]+DP[i-1][1])%9901;
        DP[i][1]=(DP[i-1][0]*2+DP[i-1][1])%9901;
    }

    result = (DP[N][0]+DP[N][1])%9901;

    cout<<result<<"\n";

    return 0;
}