백준 11726, 11727번의 수학적 해석

백준 11726번

---

백준 11726번은 2xn 타일링에 대한 문제이다.
1x2와 2x1 타일만 쓰므로 2xn 직사각형을 채웠을 때 1번째 행과 2번째 행의 모양은 같다는 것을 알 수 있다.
각 행만 따로 떼어보면 '1x1' 타일과 '2x1' 타일의 조합이 된다.

뭔가 느낌이 오지 않는가?
이 때, 문제를 다르게 해석할 수 있다. 직접 바꿔보자면,

자연수 n을 1과 2를 사용하여 덧셈으로 나타낼 수 있는 경우의 수를 구하시오.

의 문제와 같은 것을 계산하는 것을 알 수 있다.

예를 들어 숫자 4를 1과 2로 구하는 경우는

1+1+1+1
2+1+1
1+2+1
1+1+2
2+2

이렇게 5가지이다. 자세히 보면, 2가 아예 없는 계산, 2가 1개 들어가 있는 계산, 2가 2개 들어가있는 계산으로 총 세 가지 케이스로 이루어져있다.

2가 아예 없을 때는 $_4C_0$ 개, 2가 1개 있을 때는 $_3C_1$, 2가 2개 있을 때는 $_2C_2$ 이다.
2는 최대 n//2 개만큼 들어갈 수 있고 2의 갯수가 1 증가할수록 $C$ 앞의 수는 1씩 감소한다.

이를 파이썬 코드로 표현하면

<정답코드>
import math
n = int(input())
count = 0
for i in range(n//2+1):
    count+=math.factorial(n-i)//(math.factorial(i)*math.factorial(n-2*i)) # n-iCi의 콤비네이션 계산
print(count%10007)

이 된다.

백준 11727번

---

같은 방식으로 11727번을 보면 쉽게 응용이 가능하다. 2x2 타일이 추가되었기 때문에 간단히 말하자면 이 문제에서는 1x2 타일이 두 가지 스타일이 있다고 생각하면 된다.
그러므로 1과 2를 더하여 n을 만들 때, 만약 2를 i개 사용하여 만든다고 하면 위와 같은(11726번) 방식에서 $2^i$개만큼 경우의 수가 곱해지게 된다.

즉 파이썬 코드를 보면

<정답코드>
import math
n = int(input())
count = 0
for i in range(n//2+1):
    count+=(2**i)*math.factorial(n-i)//(math.factorial(i)*math.factorial(n-2*i))
print(count%10007)

위와 같다. 11726번 문제와 다른 부분은 단지 (2$**$i)가 $_{n-i}C_i$ 계산 앞에 곱해졌다는 것 뿐이다.