[BOJ] 백준 11726 2×n 타일링 (Python)

문제

11726번: 2×n 타일링

 

문제 해석

접근 방법

전형적인 DP(Dynamic Programing) 문제입니다. 각 단계를 이전 단계의 경우의 수의 합으로 나타낼 수 있습니다.

 

풀이 과정

이번 문제의 경우, 각 단계는 크게 두 가지 경우로 나눌 수 있습니다.

1. 마지막 타일이 세로 타일 한 개인 경우 (세로 타일이 두 개인 경우는 여기에 포함)
2. 마지막 타일이 가로 타일 두 개인 경우

결국 마지막에 어떤 타일이 오는 지에 따른 경우의 수의 합으로 생각할 수 있습니다.

 

전체 코드

from sys import stdin

N = int(stdin.readline().rstrip())

memo = [0] * 1001
memo[1] = 1
memo[2] = 2

for i in range(3,1001):
  memo[i] = memo[i-1] + memo[i-2]

print(memo[N] % 10007)