[정올 1411] 두 줄로 타일 깔기

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=687&sca=99&sfl=wr_hit&stx=1411 

JUNGOL

#include <stdio.h>

/*
	한 번 수학적 귀납법으로 구해보면
	F(1) = 1
	F(2) = 3 
	F(3) = 5 
	F(4) = 11
	F(N) = F(N-1) + 2*F(N-2)
*/

const int SUB = 20100529;
int N, F[100100];

int main(void) {
	F[1] = 1, F[2] = 3;
	scanf("%d", &N);
	for (int i = 3; i <= N; i++) {
		F[i] = F[i - 1] + 2 * F[i - 2];
		F[i] %= SUB;
	}
	printf("%d\n", F[N]);

	return 0;
}