[백준 파이썬] 11726 2xn 타일링

📌문제 출처

솔브닷 3+ 클래스 단계
https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

❓ 문제

❗ 풀이

• DP 활용

📗 풀이 코드

import sys
input = sys.stdin.readline
a,b=1,1
for _ in range(int(input())-1):
    a,b = b,a+b
print(b%10007)

📗 코드 해설

• 타일의 가로 방향을 어떻게 배열하느냐에 따라 세로의 배열은 정해지기에
  이 문제는 n을 1과 2로 배열하는 방법의 수를 구하는 문제가 된다.
• n에 따른 가짓수는 아래와 같이 피보나치 수열로 형성된다.
  0 -> () -> 1
  1 -> (1) -> 1
  2 -> (1,1),(2) -> 2
  3 -> (1,1,1),(1,2),(2,1) -> 3
  4 -> (1,1,1,1),(1,1,2)*3,(2,2) -> 5
  5 -> (1,1,1,1,1),(1,1,1,2)*4,(1,2,2)*3 -> 8
  6 -> (1,1,1,1,1,1),(1,1,1,1,2)*5,(1,1,2,2)*6,(2,2,2) -> 13
  7 -> 5+6 => 21
  8 -> 6+7 => 34
  9 ->  7+8 => 55
• n=5라면 n=3일 때의 조합 맨 뒤에 2를 배열하는 방법들과 n=4일 때의 조합 맨 뒤에 1을 배열하는 방법과 같으므로
  피보나치 수열이 형성되는 것이다.
• 이 때 맨 뒤에 2를 붙이고 앞의 1,2 들과 다시 섞이는 경우도 세어줘야한다고 생각할 수도 있으나,
  이는 뒤에 1을 붙이는 방법에서 모두 중복되지 않게 세어줄 수 있으므로 이 두가지를 더하기만 하면 된다.
• n=0, n=1의 가지수를 각가 a,b에 넣고 둘 모두 1로 초기화해준다.
  이후 n-1번 연산을 해서 a에는 b를, b에는 a+b를 넣어주어 피보나치 연산에 필요한 두가지 변수만 남겨둔다.
• for 반복문 이후 10007로 나머지 연산을 해준다.