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

#문제 링크

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

11727번: 2×n 타일링 2

 

#문제

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

2×n 타일링 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	33961	20295	16108	59.441%
문제
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.



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

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

예제 입력 1
2
예제 출력 1
3
예제 입력 2
8
예제 출력 2
171
예제 입력 3
12
예제 출력 3
2731

 

#답안

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] = 3
        continue

    dp[i] = dp[i-1] + 2*dp[i-2]

print(dp[n]%10007)

▲답안 설명