[지코바] 8회차 - 상수님의 2xn타일링

• 문제
  https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

---

 

 

• 문제분석
  2xn 크기의 타일을 1x2, 2x1타일로 채우는 경우의 수를 구하는 문제이다.
  언뜻보기에는 어려워 보이지만 차례대로 경우의 수를 구하다보면 피보나치 수열을 이루는 것을 알 수 있다.
  
  n=1일 때, 1가지
  n=2일 때, 2가지
  n=3일 때, 3가지
  n=4일 때, 5가지
  n=5일 때, 8가지
  ····
  
  순으로 f(n) = f(n-1) + f(n-2)의 규칙을 보인다.
  따라서 n이 1,2인 경우를 제외하고 피보나치 수열을 이용하여 답을 구해주면 된다.

---

 

• 상수님의 풀이

from sys import stdin

input = stdin.readline

tiling_method = []

n = int(input().rstrip())

for index in range(n+1):
  if index < 3:
    tiling_method.append(index)
  else:
    tiling_method.append(tiling_method[index-1] + tiling_method[index-2])

print(tiling_method[n] % 10007)

 

---

 

• 풀이 분석

input = stdin.readline

tiling_method = []

n = int(input().rstrip())

※test case인 n만 입력받아도 되는데 readline을 통해 input을 입력받고 오른쪽 공백을 삭제하신 이유가 궁금했다.

n을 입력 받을 수 있도록 하고 피보나치 수열을 저장할 list를 생성해준다.

for index in range(n+1):
  if index < 3:
    tiling_method.append(index)
  else:
    tiling_method.append(tiling_method[index-1] + tiling_method[index-2])

print(tiling_method[n] % 10007)

index가 3보다 작은경우, n = 1, n = 2일때는 리스트에 1, 2를 append해주고 

3이상인 경우에는 앞서 말했던것처럼 피보나치 수열을 이용하여 각각 append해준다. 

그리고나서 문제에서 말했던 10007을 나눈 나머지를 출력해주는데 나는 이 문제를 풀 때 이걸 해주지 않아 분명 제대로 푼것 같은데 계속 오답이 떠서 헤맸던 기억이 있다....