[백준/c++] 1309번: 동물원

 

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

1309번: 동물원

 

Nx2 우리가 있고 가로/세로 붙여서 사자를 배치하면 안 된다. 이 우리에 사자를 배치하는 경우의 수를 구하라.

N 줄의 우리가 있으니까 i(1~N) 개일 때 경우의 수를 모두 차례대로 구해보면 된다.

 

1x2 우리에서 사자를 배치하는 경우는 (1,0), (0,1), (0,0) 세 가지 경우가 있다.

이를 토대로, 마지막 줄에 위 세가지 경우를 포함한 경우의 수를 세보면 규칙이 나타난다.

 

i=2일 때는 (1,0)와 (0,1)의 경우는 2가지 (0,0)의 경우는 3가지

i=3일 때는 (1,0)와 (0,1)의 경우는 5가지 (0,0)의 경우는 7가지

 

이렇게만 봐도 규칙이 어느정도 보인다.

dp [3][0] = dp [2][1] + dp [2][2]

dp [3][1] = dp [2][1] + dp [2][2]

dp [3][2] = dp [2][0] + dp [2][1] + dp [2][2]

 

1. 초기값 정하기

dp [1][0] = dp [1][1] = dp [1][2] = 1을 초기값으로 정해준다

 

2. 점화식 구하기

위에서 규칙을 찾은 것을 바탕으로 점화식을 구한다.

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

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

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

 

#include <iostream>
#define num 100002
using namespace std;
int n;
long long dp[num][3];

void input(){
    cin >> n;
}

void solution(){
    //2*1 우리라면, (0, 1) 혹은 (1, 0), (0, 0)
    dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 1; //초기화
    
    for(int i=2; i<=n; i++){
        dp[i][0] = (dp[i-1][1] + dp[i-1][2])%9901;
        dp[i][1] = (dp[i-1][1] + dp[i-1][2])%9901;
        dp[i][2] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2])%9901;
    }
    
    cout << (dp[n][0] + dp[n][1] + dp[n][2])%9901 << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!