백준-11726번(2×n 타일링)-PYTHON3

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

---

 

st[1]=1

st[2]=2

st[3]=3

st[4]=5

st[5]=8

st[6]=13

...

st[9]=55

 

세로로 하나 세우고 나머지는 타일이 n-1개일 때의 경우의 수와 같고

가로로 두개 세우고 나머지는 타일이 n-2개일 때의 경우의 수와 같으니

점화식을 만들어보면

st[n]=st[n-1]+st[n-2]가 된다.

 

나의 코드

def dp(n):
    st=[0 for i in range(n+2)]
    st[0:3]=[0,1,2]
    for i in range(3,n+1):
        st[i]=(st[i-1]+st[i-2])%10007
    return st[n]

print(dp(int(input())))