[1309] 동물원

 

1309번: 동물원

 

---

 

💧 해결 방법

N이 1일 때, 2일 때, 3일 때, 4일 때.... 를 차근차근 계산해보면 규칙성을 바로 발견할 수 있다.

 

dp[i] = 2(가로) * i(세로) 크기의 동물원에 사자를 배치하는 방법의 수

라고 한다면

dp[0] = 1

dp[1] = 3

 

dp[2] = 7

 

dp[3] = 20

dp[4] = 41

.

.

.

즉, 아래와 같은 점화식이 성립하는 것을 알 수 있다.

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

 

---

 

☂️ 내 코드

// [1309] 동물원
// https://www.acmicpc.net/problem/1309
// dp

#include <cstdio>

int main(void)
{
    int n, dp[100001];
    scanf("%d", &n);
    dp[0] = 1; dp[1] = 3;
    
    for(int i = 2 ; i <= n ; i++) {
        dp[i] = (dp[i - 1]*2 + dp[i - 2]) % 9901;
    }

    printf("%d\n", dp[n]);
}