DP

백준_11727

2021.04.19

2×n 타일링 2

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

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

/**
* n = 1     1     |
*     2     3     || , =, ㅁ
*     3     5     |||, =|, |=, ㅁ|, |ㅁ
*     4     11    ||||, ||=, |=|, =||, ==, ||ㅁ, |ㅁ|, ㅁ||, ㅁㅁ, ㅁ=, =ㅁ
*
* d[n] = d[n-2] * 2 + d[n-1]
*/

n = int(input())

d = [1, 3, 5]

for i in range(3, n):
  d.append(d[i-2] * 2 + d[i-1])

print(d[n-1] % 10007)

Discussion and feedback