1793 타일링

2*n의 타일을 2*1,1*2,2*2 타일을 붙여서 만드는데 나올수 있는 경우의 수를 구하는 문제이다.

이런 문제는 점화식이 중요하다. 여기서 사용된 점화식은
f(0) = 1
f(1) = 1
f(n) = f(n-1) + 2*f(n-2)
이다.
이것에 맞춰서 구하면 되는데, 숫자의 길이가 기하급수적으로 증가해서 long long 형을 넘는다. 따라서 big integer의 덧셈을 구현해주어야 한다. 사실 곱셈도 구해야하지만, 덧셈을 두번해주면 되니깐.

언젠가 big integer 알고리즘을 미리 구현해둘 필요가 있다.

소스