1904 01타일

00과 1만으로 한 줄을 채우는 경우의 수를 구하는 문제입니다.

일단 일차적으로 손으로 수열을 계산해나가다 보면 1, 2, 3, 5, 8, ...처럼 피보나치 수열의 규칙이 보입니다.

따라서 연속된 세 개의 항 사이의 관계에 주목했습니다.

00과 1만으로 100칸을 채운다고 가정합시다.

마지막 자리에 1을 놓는다면, 나머지 99칸을 채우는 방법이 있습니다.

마지막 자리에 00을 놓는다면, 나머지 98칸을 채우는 방법이 있습니다.

이 두 가지 경우는 마지막 자리가 항상 다르므로 서로 겹치지 않습니다. 즉, (100칸을 채우는 방법의 수) = (99칸을 채우는 방법의 수) + (98칸을 채우는 방법의 수) 처럼 나타낼 수 있습니다.

피보나치 수와 동일한 관계에 있기 때문에, 첫 두 개의 수만 조심한다면 피보나치 수와 같은 방법으로 계산할 수 있습니다.