C++ / 백준 / 1309 / 동물원

문제

 

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

1309번: 동물원

 

문제풀이

 

경우의 수를 나눠 DP 하는 문제인 줄 알았는데 총개수를 세고 나니까 단순히 DP 하면 되는 문제였다.

N이 1일 때

배치 X: 1

한 마리 배치: N*2 = 2

= 3

 

N이 2일 때

배치 X: 1

한 마리 배치: N*2 = 4

두 마리 배치: 2

= 7

 

N이 3일 때

배치 X: 1

한 마리 배치: N*2 = 6

두 마리 배치: 8

세 마리 배치: 2

= 17

 

이런 식으로 개수를 세면 규칙이 보인다.

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

코드

#include <iostream>
#include <vector>
#define DIV 9901
using namespace std;

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

	int N(0);
	cin >> N;
	
	vector<int>answer(100001, 0);
	answer[0] = 1;
	answer[1] = 3;	
	
	for (int idx = 2; idx <= N; ++idx) {
		answer[idx] = ((answer[idx - 1] * 2) % DIV + answer[idx - 2]) % DIV;		
	}
	cout << answer[N];
}