[DP 알고리즘] 2xn 타일링 S3

기출: BOJ #11726

 

일단 기존 직사각형에서 타일을 추가하여 새로운 직사각형을 만들 수 있으므로 DP를 생각해야 한다 (확장성)

 

새로운 직사각형 D[n]을 만드는 경우는 총 두가지 케이스가 있다

 

1. 세로 타일 추가 (D[n-1])

2. 가로 타일 추가 (D[n-2])

 

따라서 점화식을 세우면 다음과 같다

 

D[n] = 2*n 직사각형을 채우는 방법의 수

D[n] = D[n-1] + D[n-2]

 

초기값은 D[1] = 1, D[2] = 2 이고 구해야 할 범위는 3~n이다

# 기존 직사각형에 타일 추가를 통해 새로운 직사각형을 만들 수 있다 (확장 가능)
# 점화식 정의
# D[n]: 2*n 타일을 채우는 방법의 수
# D[n] = (D[n-1]) + (D[n-2])
# 초기값 : D[1] = 1, D[2] = 2
# 계산 범위 : 3~n


n = int(input())

if n!=1:
    d = [0 for _ in range(n+1)]
    d[1] = 1
    d[2] = 2

    for x in range(3,n+1):
        d[x] = d[x-1] + d[x-2] 

    print(d[n]%10007)

else:
    print(1)