[백준] 11726 : 2xn 타일링 - Python

2xn 타일링

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

import sys
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline
#세로 x 가로
#작은 문제를 점진적으로 확장. 보자마자 dp
n = int(input())
dp = [0] * (10001) #dp[i]는 2xi를 채우는 방법의 수
dp[1] = 1
dp[2] = 2
for i in range(3,n+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n] % 10007)

코멘트

규칙을 살펴야 한다. 문제에서 2xn을 구하라 했는데, 주어진건 1x2, 2x1 타일 두개. 이걸 활용해서 어떻게 할건지 생각해야 한다.

• 보자마자 작은 문제를 점진적으로 확장시키는 dp가 떠올랐다.

즉 2xn이니까 n =,1,2,3... 대입해보면서 개수가 몇개인지 그리고 어떤 점화식이 떠오르는지 생각했으면 문제 접근을 잘한 것이다.

이 문제도 맨 마지막 항. 즉 마지막에 붙이는게 1x2인지 2x1인지 판단하는거 아닐까? 의심했으면 쉽게 풀었을 것.

• dp문제를 풀어보니까 느끼는 것이 dp 테이블을 딱맞춰 만드는 것이 아닌 어느정도 크게 만들어야 겠다. (최댓값) 가장 마지막에 오류가 나는 것이 문제...