[BAEKJOON] 1309

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[sliver 1, 1309 동물원] - 다이나믹 프로그래밍(DP)

N번째 줄에 사자를 배치할 수 있는 경우는 다음과 같다. (미배치(0), 왼쪽(1), 오른쪽(2))
1) 모두 없는 경우: 왼쪽, 오른쪽, 미배치 → dp[n][0] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2];
2) 왼쪽 칸에 있는 경우: 오른쪽, 미배치 → dp[n][1] = dp[n-1][0] + dp[n-1][2];
3) 오른쪽 칸에 있는 경우: 왼쪽, 미배치 → dp[n][2] = dp[n-1][0] + dp[n-1][1];

이를 종합해보면

for(int i=2;i<=N;i++) {
	dp[i][0] =  dp[n-1][0] + dp[n-1][1] + dp[n-1][2] % 9901;
	dp[i][1] =  dp[n-1][0] + dp[n-1][2] % 9901;
	dp[i][2] =  dp[n-1][0] + dp[n-1][1] % 9901;
}

이 됨을 알 수 있다
 
N이 1,2,3,4일 때의 값을 찾아 규칙을 찾아낼 수 있다.
n = 1, answer = 1;
n = 2, answer = 3;
n = 3, answer = 7(=3*2+1);
n = 4, answer = 17(=7*2+3);
n = x, answer = dp[x-1]*2 + dp[x-2];

 

#include <iostream>
#include <cmath>
#pragma warning(disable:4996)

using namespace std;

int cage[100001];
int main() {
	int N;
	scanf("%d", &N);
	cage[0] = 1;
	cage[1] = 3;
	for (int i = 2; i <= N; i++) {
		cage[i] = (cage[i - 1] * 2 + cage[i - 2]) % 9901;
	}
	printf("%d", cage[N]);
}