[C언어/DP] 1309 : 동물원

N이 증가할 때마다 새로운 케이스로 두고 풀면 오래걸린다.

이전 층 값을 누적시켜 사용한다.

#include<stdio.h>

int main(void){
	int N,answer;
	int dp[100005][3]={0,};
	scanf("%d",&N);
	dp[1][0]=1;dp[1][1]=1;dp[1][2]=1;
	for(int i=2;i<=N;i++){
		dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%9901;
		dp[i][1]=(dp[i-1][0]+dp[i-1][2])%9901;
		dp[i][2]=(dp[i-1][0]+dp[i-1][1])%9901;
	}
	answer=(dp[N][0]+dp[N][1]+dp[N][2])%9901;
	printf("%d\n",answer);
	return 0;
}