[BOJ][C++] 백준 1309번 동물원

1309번 동물원

1. 문제 정보

백준 온라인 저지 [1309번 동물원] 문제의 링크입니다.

문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.
이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.
동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

예제 입력1

4

예제 출력1

41

시간 / 메모리 제한

2초 / 128MB

---

2. 생각

1. 2Xn 모양의 우리에 사자를 채워 넣는 방법을 구하는 문제입니다. 큰 문제를 작은 문제로 쪼갤 수 있고, 작은 문제의 답을 통해 큰 문제의 답을 구할 수 있으므로 다이나믹 프로그래밍 방법을 이용하겠습니다.

2. 여기서 사자를 2Xn 우리에 놓지 않거나,
   사자를 2Xn 우리의 왼쪽에 놓거나,
   사자를 2Xn 우리에 로느쪽에 놓는 방법의 수를 구할 수 있습니다.

3. dp[n][0]을 사자를 2Xn 우리에 놓지 않는 경우의 수라고 정의하고,
   dp[n][1]을 사자를 2Xn 우리의 왼쪽에 놓는 경우의 수라고 정의하고
   dp[n][2]을 사자를 2Xn 우리의 오른쪽에 놓는 경우의 수라고 정의하겠습니다.

4. 그러면 사자를 2Xn 우리에 놓지 않을 때는 n-1의 모든 경우에 덧붙일 수 있고,
   사자를 2Xn 우리의 왼쪽에 놓을 때는 n-1의 경우에서 우리의 왼쪽에 놓았던 경우만 빼면 되겠습니다.
   그리고 반대로 사자를 2Xn 우리의 오쪽에 놓을 때는 n-1의 경우에서 우리의 오른쪽에 놓았던 경우만 빼면 되겠습니다.

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

---

3. 소스코드 (C++)

---

터미널의 입출력 화면 예제1

터미널의 입출력 화면 다른 예제1

터미널의 입출력 화면 다른 예제2