[BaekJoon] 백준 11726번 : 2xn 타일링

11726번 : 2xn 타일링

이런 문제는 처음부터 쭉 구하다 보면 규칙이 보인다.

결론 부터 말하자면 1, 2, 3, 5, 8, 13.. 이어서 피보나치와 같은 수열을 이루지만

처음에 값을 잘못 구해 규칙을 발견하지 못 했다..

피보나치 수열과 같다는 건 발견하지 못하고 n 마다 구하는 공식을 발견했다.

n 값에 맞춰 1x2 로만 채우는 경우부터 2x1 을 점점 추가해가며 만드는 방법이 있다.

예를들어 n이 9라면 111111111, 11111112, 1111122, 111222, 12222 의 방법으로 타일을 채울 수 있다.

또 각각의 경우에 2x1 타일이 위치하는 경우가 다르기 때문에 nCr 을 통해 모든 경우를 구하면 된다.

---

from math import factorial


def cal(n, r):

	return factorial(n) // (factorial(n - r) * factorial(r))


answer = 0
weight = int(input())
n = weight
r = 0

while n >= r:
	answer += cal(n, r)
	n -= 1
	r += 1

print(answer % 10007)