동물원 / DP, 점화식 세우기, 상태 점화식

동물원

분류  : DP

난이도  : 1 / 5

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

평

간단한 다이나믹 프로그램 문제이다.

2 * N의 동물원이 있는데, 사자를 가로나 세로로 연이어 둘 수 없다. 모든 사자를 배치할 수 있는 경우를 세는 것이다.

처음에 사자의 수가 없어서 사자의 수를 0마리부터 N까지 증가시키면서 세려고 하였는데, 곧 안된다는 것을 알았다.

점화식을 특별히 세울 수 없었기 때문이다.

그래서 동물원 칸수를 증가하면서 놓을 수 있는 경우를 체크하는 방향으로 코드를 작성하였다.

D( N,0 ) 은 N번째 열에 사자를 두지 않는 경우의 최대 수

D( N,1 ) 은 N번째 열에 왼쪽에 사자를 두는 경우의 최대 수

D( N,2 ) 은 N번째 열에 오른쪽에 사자를 두는 경우의 최대 수

이런식으로 설정하면 점화식을 세울 수 있다.

D[N][0] = D[N-1][0] + D[N-1][1] + D[N-1][2]        

사자를 두지 않는 경우는 그 전의 열의 없는 경우, 왼쪽에 있는 경우, 오른쪽의 있는 경우 모두를 더한 값

D[N][1] = D[N-1][0] + D[N-1][2] 

사자를 왼쪽에 두는 경우는, 그 전의 열의 없는 경우, 오른쪽에 놓았을 경우

D[N][2] = D[N-1][0] + D[N-1][1] 

사자를 오른쪽에 두는 경우는, 그 전의 열의 없는 경우, 왼쪽에 놓았을 경우

결국 N열에 둘 수 있는 모든 경우의 수는 D[N][0] + D[N][1] + D[N][2] 이다.

#include<iostream> using namespace std; #pragma warning(disable:4996) int D[100001][3]; int N; int mod = 9901; int main() { cin >> N; D[1][0] = 1; D[1][1] = 1; D[1][2] = 1; for (int i = 2; i <= N; ++i) { D[i][0] = (D[i - 1][0] + D[i - 1][1] + D[i - 1][2]) % mod; D[i][1] = (D[i - 1][2] + D[i - 1][0]) % mod; D[i][2] = (D[i - 1][1] + D[i - 1][0]) % mod; } cout << (D[N][0] + D[N][1] + D[N][2]) % mod << endl; }

식에서 mod는 문제 통과를 위한 연산(오버플로우 방지)