이 문제를 어떻게 접근해야 될지 모르겠어서 다른 Discuss를 살펴보던 중 조교님이 "저도 피보나치가 이렇게 클 줄 예상 못했어요 죄송합니다 ㅜㅜ"라고 하신 것을 보고 '앗! 이건 피보나치 수열을 쓰는 거구나' 하고 풀어서 맞추긴 했는데 다시 생각해봐도 이게 왜 피보나치 수열로 풀리는지 모르겠습니다. 타일 채우는 경우의 수가 피보나치 수열이랑 무슨 상관인지 설명해 주실 수 있을까요? ㅜㅜ

문제 하단에도 힌트를 드렸다시피, 타일을 채워넣는 방법의 수 = 맨 왼쪽에 세로로 넣는 방법의 수 + 맨 왼쪽에 가로로 넣는 방법의 수 이걸 풀어서 쓰면, 2 × n을 채워넣는 방법의 수 = 맨 왼쪽에 세로로 타일을 채우고 나머지 2 × n-1을 채워넣는 방법의 수 + 맨 왼쪽에 가로로 타일을 채우고 나머지 2 × n-2를 채워넣는 방법의 수 다시 말하면 2×n을 채워넣는 방법의 수 = 2 × n-1을 채워넣는 방법의 수 + 2 × n-2를 채워넣는 방법의 수 그리고 2×1을 채우는 방법은 한 가지, 2×2을 채우는 방법은 두 가지. 위의 내용을 점화식으로 만들면 2×n을 채워넣는 방법의 수를 f(n)이라고 할 때, f(n) = f(n-1) +f(n-2) f(1) = 1 f(2) = 2 그러므로 답은 1, 2로 시작하는 루카스수열 (하나씩 앞당긴 피보나치수열)이 됩니다 아직 함수를 배우지는 않았으나, 함수 없이 설명드릴 방법이 없네요... 9주차에 알게 될테니 이 내용은 아직 이해못해도 괜찮습니다.

아하! 그런 뜻이었군요 힌트를 봐도 무슨 소리인가 했는데 친절한 조교님 덕분에 완전히 이해 됐습니다! 감사합니다.