백준
백준 1793 타일링 (파이썬)
chldkato
2020. 3. 3. 15:46
https://www.acmicpc.net/problem/1793
1793번: 타일링
문제 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. 출력 입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다. 예제 입력 1 복사 2 8 12 100 200 예제 출력 1 복사 3 171
www.acmicpc.net
한 칸을 채우는 방법은 세로로 타일을 배치하는 방법 하나
두 칸을 채우는 방법은 가로로 타일을 2개 배치하는 방법과 2x2 타일을 배치하는 방법 2개
따라서 a[i] = a[i-1] + 2 * a[i-2]
import sys
input = sys.stdin.readline
def cnt(n):
if n == 0 or n == 1:
return 1
a = [0 for _ in range(n+1)]
a[0], a[1] = 1, 1
for i in range(2, n+1):
a[i] = a[i-1] + 2 * a[i-2]
return a[n]
while True:
try:
print(cnt(int(input())))
except:
break