[C] 백준 - 1309번: 동물원

6월 24일(월) - 다이나믹 프로그래밍(1309번)

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

---

최초 생각 정리

---

문제점

---

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int dp[3][100001];

int main(void)
{
	int N;
	scanf("%d", &N);

	dp[0][1] = dp[1][1] = dp[2][1] = 1;

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

	printf("%d", (dp[0][N] + dp[1][N] + dp[2][N]) % 9901);
	return 0;
}

---