[BOJ/백준] 11726 - 2×n 타일링 (Python)

문제

문제링크

2*n 크기의 직사각형을 1*2(가로타일), 2*!(세로타일) 타일로 채우는 방법의 수를 10007로 나눈 나머지를 구하라.

 

풀이

n=1일 경우 2*1 타일 한 개만 사용할 수 있다. 이를 if문으로 예외로 빼둔다.

이외에는 dp에 방법의 수를 저장한다.

dp[1]=1이고 dp[2]=2(각 타일로만 이루어짐)이다.

만약 맨 끝에 가로타일을 놓게 된다면 그 전까지의 직사각형 크기는 2*(n-2)이므로 dp[n-2]와 같다.

세로 타일을 놓으면 dp[n-1]이다.

dp[n]은 이 두가지 경우를 모두 포함해야 하므로 둘의 합으로 정의한다.

for문으로 n까지 위 과정이 반복되면 dp[n]값을 10007으로 나눈 나머지를 출력한다.

 

코드

import sys
input=sys.stdin.readline

n=int(input())
dp=[0]*(n+1)

if n==1:
    print(1)
else:
    dp[1],dp[2]=1,2
    for i in range(3,n+1):
        dp[i]=dp[i-2]+dp[i-1]
    print(dp[n]%10007)