[BOJ] 11727 - 2×n 타일링 2

[BOJ] 11727 - 2×n 타일링 2

문제

문제

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

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

입력

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

출력

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

예제 입력

2

예제 출력

3

문제 해결

지난 번에 풀어보았던 2×n 타일링과 유사하지만 생각해야하는 것이 한가지 더 있다. 2x2 타일이 추가되었다는 점이다. 이점을 유의해서 점화식을 세워보자

index	0	1	2	3	4	5
dp	0	0	0	0	0	0

index 가 1인 경우는 2x1 하나를 놓는 경우 1가지 이다.

index가 1인 경우

if i == 1 :
    arr[i] = 1

index 가 2인 경우는 2x1 타일 두개를 겹쳐 놓는 경우 2가지와 2x2 타일을 놓는 경우 1가지 그래서 총 3가지이다.

index가 2인 경우

elif i == 2 :
    arr[i] = 3

index 가 3 이상인 경우는 dp[3-1] 경우에 2x1 타일을 붙이는 경우와 dp[2-1] 에 2x1 타일 2개를 가로로 붙인 경우, 2x2 타일을 붙인 경우가 있다. 2x1 타일을 세로로 붙이면 안되는 이유는 지난 2xn 타일 붙이기 포스팅에 그림으로 설명되어 있다.

index가 3 이상인 경우

else :
    arr[i] = arr[i-1] + arr[i-2] * 2

코드를 작성해 보자.

python 코드

n = int(input())
arr = [0] * (n+1)
for i in range(1, n+1):
    if i == 1 :
        arr[i] = 1
    elif i == 2 :
        arr[i] = 3
    else :
        arr[i] = arr[i-1] + arr[i-2] * 2

print(arr[n] % 10007)

Test Case

45665
3559
------------------------
65704
9180
------------------------
25088
8817
------------------------
35023
3338
------------------------
60442
6144
------------------------

느낀점

화이팅