이 문제는 백준 알고리즘 분류 중에 대표적인 Dynamic Programming 문제이다. 본인은 고민하는 중에 조합으로 푸는 방법은 택하였고 Python3 에서 아슬아슬하게 통화하였다.
문제 이해 및 적용하기
문제 설명은 따로 할 필요 없을 정도로 간단하다. 그대로 인용하면 2*n 크기의 직사각형을 1 * 2, 2 * 1 타일로 채우는 방법의 수를 구하는 것이다.
이 문제를 가장 처음 접근 할 때에 어차피 2 * 1 타일은 항상 2개를 써야한다.
그러므로 이 경우는 2 * 2로 보아도 무관하며 2 * 2와 1*2의 타일의 모든 경우의 수를 구하는 것이니
직사각형에서 *2는 없애버려도 무관하다.
그러면 최종적으로 n개의 크기의 배열을 크기 1과 2로 채울 수 있는 경우의 수와 동일하게 된다. 이 가정 안에서 경우의 수를 1부터 나열해보면
1 번째 : 1
2번째 : 11 2
3번째 : 111 21 12
4번째 : 1111 112 121 211 22
5번째 : 11111 11112 11121 11211 12111 21111 2211 2121 2112 1221 1212 1122
임을 알 수 있다.
1 번째 : 1C0
2번째 : 2C0 + 1C1
3번째 : 3C0 + 2C1
4번째 : 4C0 + 3C1 + 2C2
5번째 : 5C0 + 4C1 + 3C2
2인 숫자를 조합에서의 __골라진 숫자__로 가정했을 때에 위와 같이 표현할 수 있다.
이와 같이 점화식을 세워보면
n번째 : nC0 + n-1C1.. n-rCr (n-r>=r) 이다.
코드로 나타내면 이 과정은 다음과 같다.
# execution
ans = 0
temn = n
r = 0
while(temn>=r):
ans+=com(temn,r)
r+=1
temn-=1
print(int(ans)%10007)
주의할 점
- python에서 지원해주는 combintation은 list를 만들어 주는 것이기 때문에 정수형으로 함수를 따로 만들어주어야 한다.
전체코드
import sys
import operator as op
from functools import reduce
input = sys.stdin.readline
n = int(input())
# combination
def com(x,y):
if x < 1 or y <0 or x < y:
raise ValueError
y = min(y, x-y)
numerator = reduce(op.mul,range(x,x-y,-1),1)
denominator = reduce(op.mul, range(1, y+1),1)
return numerator // denominator
# execution
ans = 0
temn = n
r = 0
while(temn>=r):
ans+=com(temn,r)
r+=1
temn-=1
print(int(ans)%10007)