0211_알고리즘 백준 #11727. 2×n 타일링 2

문제

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

11727번: 2×n 타일링 2

 

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

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

---

입력

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

---

출력

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

---

코드

1. 함수 구현

n = int(input())

def rec(n):
    if n == 1:
        return 1
    elif n == 2:
        return 3
    else:
        return (2 * rec(n - 2) + rec(n - 1))
    
print(rec(n) % 10007)

 

예제 결과 출력

$ C:/Users/PC/AppData/Local/Programs/Python/Python39/python.exe 
2
3

$ C:/Users/PC/AppData/Local/Programs/Python/Python39/python.exe      
8
171

$ C:/Users/PC/AppData/Local/Programs/Python/Python39/python.exe
12
2731

 

※ VScode에서는 제대로 출력

 

※ 백준 제출 시 시간 초과

 

2. 리스트 구현

n = int(input())

rec = [0] * 1001

rec[1] = 1
rec[2] = 3

for num in range(3, n + 1):
    rec[num] = 2 * rec[num - 2] + rec[num - 1]

print(rec[n] % 10007)

 

※ 처음엔 런타임 에러(IndexError)가 났었는데 list의 크기를 n + 1에서 1001로 변경하니 맞았다.

    n이 1부터 1000까지 가능하므로 전체 n의 크기인 1000에 1을 더한 1001만큼의 크기가 필요했나보다.