[python] 백준 11726 - 2xn 타일링

출처 : 백준, https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

첫 번째 풀이 : 실패

 

if __name__ == '__main__':
  n = int(input())
  count_arr = [0] * (n+1)

  count_arr[1] = 1
  count_arr[2] = 2

  for i in range(3, n+1):
    count_arr[i] = count_arr[i-1] + count_arr[i-2]

  print(count_arr[n] % 10007)

 

runtime 에러가 나길래 뭔가 했더니만 1일 때 예외처리 안해줬더라.

 

 

두 번째 풀이 : 성공

 

if __name__ == '__main__':
  n = int(input())
  count_arr = [0] * (n+1)

  count_arr[1] = 1
  try:
    count_arr[2] = 2
  except:
    pass

  for i in range(3, n+1):
    count_arr[i] = count_arr[i-1] + count_arr[i-2]

  print(count_arr[n] % 10007)

 

그냥 뭔가 엄청난 발견이 있는건 아니고.....

2x5까지 해보니까 count[i]= count[i-2] + count[i-1] (i>2), count[1] = 1, count[2] = 2더라......

점화식으로 표현할 수 있으니까 DP........

 

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

-