[1309번] 동물원

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

아래 그림을 통해 상세히 설명하였다.

DP의 0~2는 직접 구해서 상수로 두고 그 이후 값을 점화식을 통해서 구한다.

점화식에 대한 상세한 내용은 아래 그림 및 설명을 통해 달아두었다.

DP[0] = 1 (한 마리도 없는 경우도 1로 취급)

DP[1] = 3 (왼쪽, 오른쪽, 없는 경우)

DP[2] = 7

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#include <iostream> #include <cstdio>   using namespace std;   int DP[100002];   int main() {     int n;       scanf("%d", &n);       DP[0] = 1;     DP[1] = 3;     DP[2] = 7;          for (int i = 3; i <= n; i++)         DP[i] = (DP[i - 1]*2 + DP[i - 2]) % 9901;          cout << DP[n];     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus