tiling

개발공부/algorithm

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

백준 1793 타일링 Silver I 문제링크 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 나의 접근 DP로 타일링에 대한 규칙을 찾고 그에 대한 점화식을 찾아내는 문제다. 한 칸을 채우는 방법은 세로로 타일을 배치하는 방법 하나, 두 칸을 채우는 방법은 가로로 타일을 2개 배치하는 방법과 2x2 타일을 배치하는 방법 2개이기 때문에 arr[i] = arr[i - 1] + 2 * arr[i - 2] 과 같은 점화식이 나온다. N = 0 인 경우에도 답은 1이고 (아무것도 안하는 방법도 하나의 방법이기 때문), 명시되지 않는 M개의 테스트케이스를 한 번에 인풋으로 받아..