11726번: 2 x N 타일링

문제

• 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
• 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

아이디어

1x2 : bar 모형 / 2x1: wide 모형

• 2x1일때 : 1가지
  • bar 1개 : 1개
• 2x2일때 : 2가지
  • bar 1개 : 1개
  • wide : 1개

• 2x3일때 : 3가지
  • bar 1개 : 2개
  • bar 2개 : 1개

• 2x4일때 : 5가지
  • bar 2개: 3가지
  • bar 4개: 1가지

• 2x5일때 : 8가지
  • bar 1개 : 3개
  • bar 2개 : 4개
  • bar 3개 : 1개

• 2x6일때: 13가지…?
  • bar 2개 : ??
  • bar 4개 : ???
  • bar 6개 : 1개

규칙 1

• if n = 홀수
  • 1 ~ n%2 개까지 bar로 채우는 가짓수가 나온다.
• if n = 짝수
  • 2, 4, … n개까지 bar로 채우는 가짓수가 나온다.

규칙 2

• [n]번째 = [n-1]번째 + [n-2]번째

코드

• 10007로 나눠달라고 한 이유: 너무 수가 커지니까.
• 따라서, 중간 for문에서부터 10007로 나눈 나머지 처리 작업을 넣는다.
• 처음에 이걸 추가 안했더니 속도가 굉장히 느려졌다.

import sys
input = sys.stdin.readline

n = int(input())
graph = [0 for _ in range(n+1)]
graph[0], graph[1] = 1, 2
for i in range(2, n+1):
		graph[i] = (graph[i-1] + graph[i-2]) % 10007

print(graph[n-1])