[백준]1309 동물원

2017-12-01 96 words One minute

Contents

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

풀이:

a[i] 가 2 x i 칸에 채울 수 있는 배치의 최댓값이라 하자.
a[i] = 2 * a[i - 1] + a[i - 2] 로 구할 수 있다.

코드:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


#include <iostream>
using namespace std;

int main(void) {
	int n;
	cin >> n;
	int a[100001] = { 3,7,0 };
	for (int i = 2; i < n; i++) {
		a[i] = (2* a[i - 1] + a[i - 2]) % 9901;
	}
	cout << a[n - 1] % 9901 << endl;
	return 0;
}