01타일

https://www.acmicpc.net/problem/1904

틀린 풀이

• 계속 런타임 에러

• dp가 아니라, 수학적으로 풀었음

• 팩토리얼로 풀었음

  맞는 풀이

• d[i]

  • 길이가 i 일때, 만들 수 있는 수열의 개수
  • d[i-2] + d[i-1]

• 길이가 i인 수에는

  • 길이가 i-1인 수에
  • 00을 붙이거나
  • 1을 붙여서 만들 수 있다.
  • 하지만 00은 길이가 2 이기때문에, 붙일 수 없다.

• 따라서

  • i-2번째에 00을 붙이거나
  • i-1번째에 1을 붙인다

• 여기서 문제,

  • i-2번쨰에 11을 붙여서 만들 수 있지 않나?
  • 중복의 문제가 발생한다

• 따라서,

  • i-2번째 수열에, 00을 맨 뒤에 붙이고
  • i-1번째 수열에, 1을 맨 앞에 붙인다