DynamicProgramming_1_08_2xn 스타일링(11726)

문제

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

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

입력

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

출력

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

풀이

규칙을 살펴보자.

• n이 1일때 방법의 수는 1개.
  2 - 2개
  3 - 3개
  4 - 5개
  5 - 8개
• 보면 n의 방법의 수는 n - 2 + n - 1 이라고 보면 된다.
• n - 2의 경우의 수에 누워있는 두개의 타일이 붙고,
• n - 1의 경우의 수에 세워져있는 한개의 타일이 붙는다.

코드

s = [0, 1, 2]
for i in range(3, 1001):
  s.append(s[i - 2] + s[i - 1])
n = int(input())
print(s[n] % 10007)

배운 것

코멘트