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

11727번 : 2xn 타일링 2

[BaekJoon] 백준 11726번 : 2xn 타일링 이 문제에서 타일을 한 개 더 추가한 경우의 문제이다.

앞서 문제처럼 n이 9라면 111111111, 11111112, 1111122, 111222, 12222 의 방법으로 타일을 채울 수 있다.

이 때 편의를 위해 2*2 타일을 4 라고 한 뒤 경우를 따져본다면

1111122 에서 1111124, 1111142, 1111144 의 경우가 더 있을 수 있다.

때문에 nCr * 2^r 의 식으로 계산을 해 주면 답을 구할 수 있다.

---

from math import factorial


def cal(n, r, k):

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


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

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

print(answer % 10007)