백준 11726번 : 2×n 타일링

<문제>

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

11726번: 2×n 타일링

---

<코드>

import sys
input = sys.stdin.readline

n = int(input())
count = [[0 for i in range(n+1)] for j in range(2)]
count[0] = [1 for i in range(n+1)]
count[0][0] = count[1][0] = 0
for i in range(1, n+1):
    if i <2:
        count[1][i] = count[0][i]
    elif i ==2:
        count[1][i] = count[0][i] + 1
    else:
        count[1][i] = count[1][i-1] + count[1][i-2]
result = count[1][n] % 10007
print(result)

---

<풀이>

1x2 직사각형을 사용하는 경우 반드시 1x2 직사각형을 하나 더 사용해야 한다. 즉, 1x2 직사각형과 2x1 직사각형을 사용하지만 2x1 직사각형과 2x2 정사각형을 사용하는 문제로 봐도 무방하다. 

2xn 크기의 직사각형을 2x1, 2x2 사각형으로 채우는 문제이므로 n을 1과 2의 합으로 표현할 수 있는 가짓수를 구하면 된다.

---

참고 : https://github.com/Junuux/Algorithm/tree/main/Silver/11726

GitHub - Junuux/Algorithm