PS/BOJ

[백준 11727번] 2×n 타일링 2 파이썬 풀이

76 2024. 1. 19. 00:03
728x90

2×n 타일링 2 


1 초 256 MB 71346 42391 34114 58.844%

문제

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

 

기본적인 아이디어는 백준 11726번 : 2xn 타일링 과 같다.

가로의 길이가 1, 2일때는 당연하게도 1, 3이 될것이고

 

가로의 길이가 3이상으로 넘어갈때부터는 두가지 선택지가 존재한다.

 

1. 2x2 블록에 2x1 일자블록(ㅣ)을 붙여서 2x3블록을 만든다.

=> dp[2]와 경우의 수가 같다.

 

2. 2x1블록에 2x1블록 2개(=) 혹은 2x2블록(ㅁ)을 붙여 2x3 블록을 만들 수 있다.

=> dp[1]와 경우의 수에 x2를 한 값과 같다. (=를 붙이거나, ㅁ을 붙이거나)

 

위의 과정을 통해 다음과 같은 점화식을 세울 수 있다.

 

dp[n] = dp[n-1] + dp[n-2] * 2 ( 단, dp[1] = 1 , dp[2] = 2, n>=3)

 

코드는 아래와 같다.

n = int(input())

# dp 테이블 작성
dp = [0]*(n+1)

for i in range(1, n+1):
    if i == 1:
        dp[i] = 1  # 2 x 1 크기는 1개
    elif i == 2:
        dp[i] = 3  # 2 x 2 크기는 3개(||,=,ㅁ)
    else:
        dp[i] = dp[i-1] + 2*dp[i-2]  # i-2인 경우는 =이 붙거나 ㅁ이 붙을수 있기 때문에

# 모듈러 연산하여 출력
print(dp[n] % 10007)