앞에 붙이거나 뒤에 붙이냐 이런걸 나눠서 따질 필요가 없습니다. 가능한 모든 경우의 수를 두 가지로 나눌 수 있습니다.
* 00으로 끝나는 경우
* 1로 끝나는 경우
이 두가지의 개수를 각각 세서 더하면 원래 구하는 거라는 건 자명합니다. (자명하지 않다고 느껴지시면 저 경우들이 서로 겹치지 않음을 보이고 원래 경우가 무조건 저것들 중 하나에는 속함을 보이시면 되겠네요. 그럼 양쪽으로 injection이니까 개수가 같겠죠.)
각각은 어떻게 세냐, 그거는 저 각 경우들이 원래 문제에서 개수만 다른 상황이라는 점을 고려해서 점화식 꼴로 식을 세우면 되겠죠.
시작 부분이든 끝 부분이든 꼭 채워야만 하는 부분을 어떻게 채우느냐로 케이스를 나누면 됩니다.
chltjrwns1gh 4년 전
이것저것 해보니까 a_1 = 1, a_2 = 2, a_n = a_(n-1) + a_(n-2)인 피보나치 수열인 것을 알 수 있었습니다.
그런데 이게 잘 와닿지가 않습니다.
n짜리 길이 타일을 만들때 쓸 수 있는 타일의 조각은 길이1짜리, 길이2짜리가 있고
n을 만드려면 n-1에다가 1짜리를 갖다 붙이거나, n-2에다가 2짜리를 갖다 붙이면 된다는 설명을 하신 분이 있었는데
그렇게 따지면 각 타일을 앞에 붙이냐 뒤에 붙이냐, 겹치는거는 얼마나 되냐 이런것도 고려해야된다는 생각을 했습니다.
막상 그렇게 고려해서 구해보려고 하니까 잘 안나와서 오히려 nCr로 길게 써서 증명한 다음에 풀었습니다.
뭔가 직관적인 방식으로 이 문제 설명해주실 수 있는 분 계신가요..?