[DP] 백준 11726번 “2xn 타일링” Python 풀이

문제 링크

• https://www.acmicpc.net/problem/11726

풀이

• 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
  • 타일은 1x2 이나 2x1 타일 중 한가지 종류만 사용해서 채워도 괜찮습니다.
• 해당 문제는 단순한 점화식으로 해결할 수 있습니다.
  • dp[i] = dp[i-1] + dp[i-2]
• 세부 알고리즘은 아래 예제 코드와 같습니다.

코드

import sys

n = int(sys.stdin.readline())

# dp 테이블
dp = [0] * 1001

# 초기값 설정
dp[1] = 1
dp[2] = 2

# bottom-up 진행
for i in range(3, n+1):
   dp[i] = dp[i-1] + dp[i-2]

print(dp[n] % 10007)