[백준 1309] 동물원 (C++)

문제 링크: https://www.acmicpc.net/problem/1309

1309번: 동물원

1. 주의할 점

- DP문제다. 백트레킹으로 접근할 생각하지 말자

- DP문제라는건 알았지만 점화식을 세우는게 쉽지 않다. 문제를 해결하고 다른사람들의 점화식을 확인해본 결과 나와      같은 점화식은 찾지못했다(내가 너무 어렵게 해결한것 같다).

 

2. 구현

- 우선 나는 0,1로 이루어진 비트라고 생각하고 접근했다(문제와 달리 행:2 , 열:N이라고 가정)

- DP[숫자의 길이(=N)][마지막에서 2번째 번호][마지막 번호] 의 형태로 배열을 세웠다.

  ex)[N][0][0] : N의 길이면서 마지지막이 00으로 끝나는 수, [N][0][1]: N의 길이면서 마지막이 01로 끝나는 수

- 위의 DP배열을 정리하자면 다음과 같다

  DP[N][0][0] 의 경우 DP[N-1][1][0]과 DP[N-1][0][0]의 연산으로 만들 수 있다. 

  DP[N][0][1] 의 경우 DP[N-1][0][0]과 DP[N-1][1][0]의 연산으로 만들 수 있다. 

  DP[N][1][0] 의 경우 DP[N-1][0][1]과 DP[N-1][1][1]의 연산으로 만들 수 있다. 

  DP[N][1][1] 의 경우 DP[N-1][1][1]과 DP[N-1][0][1]의 연산으로 만들 수 있다. 

- "사자는 가로와 세로 인접한 칸에 모두 위치 할 수 없다"를 기반으로 다음과 같은 식이 성립한다.

  0(기존의 마지막 숫자) -> 0(새로 추가된 숫자) : X 1

  0(기존의 마지막 숫자) -> 1(새로 추가된 숫자) : X 2

  1(기존의 마지막 숫자) -> 0(새로 추가된 숫자) : X 1

  1(기존의 마지막 숫자) -> 1(새로 추가된 숫자) : X 1

- 위의 모든식을 정리하면 다음과 같은 식이 도출된다(MOD = 9901)

DP[i][0][0] = (DP[i - 1][0][0] + DP[i - 1][1][0]) % MOD;
DP[i][0][1] = ((DP[i - 1][0][0] * 2) % MOD + (DP[i - 1][1][0] * 2) % MOD) % MOD;
DP[i][1][0] = (DP[i - 1][0][1] + DP[i - 1][1][1]) % MOD;
DP[i][1][1] = (DP[i - 1][1][1] + DP[i - 1][0][1]) % MOD;

 

#define MOD 9901
#include <iostream>
using namespace std;
long long dp[100001][2][2];		//자리수, 뒤에서 2번째 숫자, 뒤에서 1번째 숫자

int main() {
	int num;
	cin >> num;
	if (num == 1) cout << 3;
	else {
		dp[2][0][0] = 1;
		dp[2][0][1] = 2;
		dp[2][1][0] = 2;
		dp[2][1][1] = 2;
		for (int i = 3; i <= num; i++) {
			dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % MOD;
			dp[i][0][1] = ((dp[i - 1][0][0] * 2) % MOD + (dp[i - 1][1][0] * 2) % MOD) % MOD;
			dp[i][1][0] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
			dp[i][1][1] = (dp[i - 1][1][1] + dp[i - 1][0][1]) % MOD;
		}
		long long result = 0;
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++) {
				result += dp[num][i][j];
				result %= MOD;
			}
		cout << result % MOD;
	}
	system("pause");
	return 0;
}