[백준][python] 1793.타일링 - DP

• 백준 1793 타일링 Silver I
• 문제링크

1793번: 타일링

나의 접근

DP로 타일링에 대한 규칙을 찾고 그에 대한 점화식을 찾아내는 문제다. 

한 칸을 채우는 방법은 세로로 타일을 배치하는 방법 하나, 두 칸을 채우는 방법은 가로로 타일을 2개 배치하는 방법과 2x2 타일을 배치하는 방법 2개이기 때문에 arr[i] = arr[i - 1] + 2 * arr[i - 2] 과 같은 점화식이 나온다.

N = 0 인 경우에도 답은 1이고 (아무것도 안하는 방법도 하나의 방법이기 때문), 명시되지 않는 M개의 테스트케이스를 한 번에 인풋으로 받아야 하는 점을 고려하지 않아서 처음에 많이 헤맸었다. ㅠㅠ 문제를 더 꼼꼼히 읽고 조건처리 확실히 하는 연습을 해야겠다.

import sys

def calc(N):
    arr = [0] * (N + 1)
    if N > 1:
        arr[0], arr[1] = 1, 1
        for i in range(2, N + 1):
            arr[i] = arr[i - 1] + 2 * arr[i - 2]
        return (arr[N])

    else:
        return 1

while True:
    try:
        print(calc(int(sys.stdin.readline())))
    except:
        break