[알고리즘]BOJ_11726_2xn 타일링(파이썬 continue, 다이나믹 프로그래밍, 나머지 연산)

#문제 링크

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

#문제

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

2×n 타일링

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	79385	29520	21526	34.903%
문제
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

 

#답안

import sys
input=sys.stdin.readline

#n을 입력받는다.
n=int(input())

#dp테이블을 생성해놓고 0으로 초기화한다.
dp=[0]*(n+1)

#for문은 1부터 n까지 돌린다.
for i in range(1,n+1) :
    if i==1 :
        dp[1] = 1
        continue
    elif i==2 :
        dp[2] = 2
        continue
    dp[i]=dp[i-1]+dp[i-2]

print(dp[n]%10007)

▲답안 설명

앞서 만든 타일들에 가장오른쪽에 가로로 혹은 세로로 붙여서 타일을 만들다 보면

d[n]=d[n-1]+d[n-2]라는 식이 나온다!(d[n]은 2*n직사각형을 채우는 방법의 수)