[python/파이썬] 백준 11727 2xn 타일링2

문제

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

 

 

[문제 풀이]

 

세로 길이가 2로 고정되어 있기에 가로길이만 신경 쓰면 되는 문제이다.

즉 1과 2의 조합으로 n을 만드는 문제이다.

 

하지만 2xn 타일링1과는 다르게 2를 표현하는 방법이 2가지이기에 ( 1 x 2 or 2 x 2) 

dp[n-2]를 두 번 더해줘야 한다.

 

따라서

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

 

 

[소스 코드]

주의할 사항은 출력이 10,007로 나눈 나머지 값이라는 점이다.

맞는 코드를 적어도 이 부분 때문에 틀릴 수 있다.

n = int(input())

dp = [0,1,3]

for i in range(3,n+1):
    dp.append(dp[i-1]+ 2*dp[i-2])
    
print(dp[n]%10007)

 

[2xn 타일링 문제 풀이 링크]

https://sodehdt-ldkt.tistory.com/64