[python] 백준 11727번 2 X n 타일링 2

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

11727번: 2×n 타일링 2

 

 

 

 

 

---

 

💻 코드

 

import sys

input = sys.stdin.readline

d = [0] * 100001


def rectangle_count(x):
    d[1] = 1
    d[2] = 3

    for i in range(3, x + 1):
        d[i] = d[i - 1] + (d[i - 2] * 2)

    return d[x]


n = int(input())

print(rectangle_count(n) % 10007)

 

 

 

 

📝 풀이

 

이 문제는 저번에 풀었던 11726번 문제에서 약간 변형된 문제였다.

 

풀이는 11726번과 거의 같으므로 자세한 풀이는 아래 게시물을 참고하기 바란다.

 

2022.07.12 - [Algorithm 문제 풀이/python] - [python] 백준 11726번 2 X n 타일링 문제 풀이

[python] 백준 11726번 2 X n 타일링 문제 풀이

 

 

 

이 문제에서 변형된 부분은 원래 2x1과 1x2 타일로만 채우는 방법의 수만 구하는 것이었는데 이번에는 2x2 타일로도 채우는 방법의 수도 포함시키라는 것이었다. 그림을 그려보니 의외로 간단했다. 아래에 있는 그림에서 볼 수 있듯이 이전 문제와 방법은 동일하고 2x2 타일을 추가했기 때문에 n - 2 부분이 2가지 방법으로 나뉘는 것이어서 이 부분만 x2만 해주면 되었다.