백준 1309 동물원 (C++)

1309번: 동물원

dp를 활용한 문제이다. 우선 하나씩 그려보면서 경우의 수를 N=1부터 세어보았다.

• N=1, 경우의 수는 3
• N=2, 경우의 수는 7
• N=3, 경우의 수는 17
• N=4, 경우의 수는 41

N일 때 경우의 수를 dp[N]이라고 한다면 점화식은 아래와 같다.

dp[N] = dp[N-1] * 2 + dp[N-2]

문제에서는 이를 9901로 나눈 나머지를 출력하라고 했으므로 각 계산마다 9901로 나누어주었다.
문제자체는 어렵지 않게 아이디어를 떠올릴 수 있었다. 그러나 9901로 나눈다는 부분을 보지 못해 시간 낭비를 좀 했다. 문제를 잘 읽고 풀도록 하자.

---

#include <iostream>

using namespace std;

int N;
long long dp[100001];

void solution() {
	dp[0] = 1;
	dp[1] = 3;

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

	cout << dp[N];
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;

	solution();
	
	return 0;
}