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

문제

 

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

---

기본 풀이

해당 문제는 dp로 풀 수 있습니다.
하나씩 채워 나간다고 생각했을 때, 채울 수 있는 방법은 2가지입니다. 세로 직사각형 채우기, 가로 직사각형 채우기입니다.
하지만, 가로 직사각형은 칸을 채우기 위해 가로 직사각형을 겹쳐서 2개씩 (정사각형 모양으로) 채워야만 합니다.
1. 두 단계 전(dp[i-2]) + 정사각형(가로 직사각형 두 개)
2. 한 단계 전(dp[i-1]) + 직사각형(세로 직사각형 한 개)
이렇게 두 가지로 나눠볼 수 있기에, dp[i] = dp[i-2]+dp[i-1] 의 반복으로 구할 수 있습니다

 

코드 풀이

그러나, 고민을 해보면 다른 수학적 방법이 있습니다.
직관적으로 가장 간단하게 채우는 법은 세로 직사각형을 다 채워 버리는 것입니다.
그 다음은 세로 직사각형 2개를 가로 직사각형 2개(정사각형 형태)로 치환해버리는 것 입니다.
그 다음은 세로 직사각형 4개를 가로 직사각형 4개(정사각형 2개)로 치환해버리는 것 입니다.
이 과정의 반복으로 생각해볼 수 있습니다.

N이 5라면, 처음은 세로 직사각형 5개. -> 총 5개 단위 중에 선택할 것 없음 -> 5C0
그 다음은 세로 직사각형 3개, 정사각형 1개(직사각형 2개). -> 총 4개 단위 중에 1개 선택 -> 4C1(조합)
그 다음은 세로 직사각형 1개, 정사각형 2개(직사각형 4개). -> 총 3개 단위 중에 2개 선택 -> 3C2(조합)

이렇게 되므로 수학적으로 조합을 계산하여 아래와 같이 구할 수 있습니다.

---

Code

import math

N = int(input())
answer = 0
for i in range(N, -1, -2):
    temp = (N-i)//2
    answer += math.factorial(i+temp)//(math.factorial(i)*math.factorial(temp))

print(answer%10007)