#1309 동물원(Dynamic Programming)

이번 문제는 Silver I 문제입니다.  이 문제를 풀기 위해서는 적절한 식을 세워야 하는데, 이것이 어느정도 훈련이 되지 않으면, 어렵습니다.

동적 프로그래밍은 점화식이 주어지지 않는 경우가 많습니다.  사실 동적 프로그래밍 뿐만 아니라 분할정복 관련된 문제들이 대부분 그렇습니다.

 

문제에서 식을 유도하고, 그 식을 수학적으로 정리하는 것이 필요합니다.  문제 난이도는 높지 않지만, 수학적으로 식을 유도하고, 정리하는 것이 필요해서 그 과정을 설명하고자 합니다.

 

Lion at Zoo Cage

2xN 동물원에 사자를 배치하는데, 가로와 세로로 연달아 배치 못하게 하는 경우의 수는 얼마인가가 문제입니다.

 

2칸씩 N개가 세로로 배치되는 것이니까, 2칸에 대해서 나올 수 있는 상태는 사자가 하나도 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 오른쪽에 있는 경우로 나눌 수 있습니다.  이를 0, 1, 2 라는 숫자로 배열하도록 합니다.  1과 2는 연속으로 나올 수 없습니다.  N 이 5인 경우를 예로 든다면 다음과 같이 할 수 있습니다.  끝수가 0, 1, 2 인 경우로 나누어서 생각해보면,

 

N	0	1	2	Total
1	1	1	1	3
2	3	2	2	7
3	7	5	5	17
4	17	12	12	41
5	41	29	29	99

 

이것을 각자 나누어서 \(d_{k0}\), \(d_{k1}\), \(d_{k2}\) 를 구한 다음에 \(d_k\)를 구할 수 있지만, 여기서는 \(d_k\)를 구해서 해보도록 합니다.

 

\[d_{k0} = d_{k-1,0} + d_{k-1,1} + d_{k-1,2} = d_{k-1}\]

\[d_{k1} = d_{k-1,0} + d_{k-1,2}\]

\[d_{k2} = d_{k-1,0} + d_{k-1,1}\]

 

사실 \(d_{k1} = d_{k2}\)이므로 그것을 고려해서 계산하면,

 

\[d_k = d_{k0} + 2d_{k1} = d_{k-1} + 2d_{k-1,0} + d_{k-1,1}+d_{k-1,2}\]

 

그런데, \(d_{k0} = d_{k-1}\)이므로,

 

\[d_k = 2d_{k-1} + d_{k-2}\]

 

라는 점화식을 얻을 수 있습니다.

 

이 점화식을 얻었으면, 이를 이용해서 프로그램을 작성하면 됩니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//------------------------------------------------------------------------------
//  baekjoon #1309
//    - by Aubrey Choi
//    - created at 2019-10-09
//------------------------------------------------------------------------------
#include <stdio.h>
#define  MOD  9901

int main()
{
  int n, dp[2]={1,3};
  scanf("%d", &n);
  for(int i=0;i<n/2;i++)
  {
    dp[0]=(2*dp[1]+dp[0])%MOD;
    dp[1]=(2*dp[0]+dp[1])%MOD;
  }
  printf("%d\n", dp[n&1]);
}