BOJ 2302

이 문제도 점화식을 세우는데...
한 번 틀린 다음에 점화식을 세우려고 생각을 해봤는데... 생각이 잘 안난다.
그래서 케이스를 직접 써보면서 3개짜리에서 시작해서 4개 5개 이렇게 늘려나가다 보니까

3개짜리에서 (1, 2, 3으로 이루어진..) 4개짜리로 늘릴 때, 4를 추가하는데
일단 3개짜리에 4를 뒤에 붙여버리면 A3개가 나오고, 그 중에서 4와 3개짜리의 맨 뒷자리를 교체할 수 있는 경우가 추가되는데... 이 경우는 A2이다. 바로 3개짜리를 만들 때 2개짜리의뒤에 3을 붙이기만 한 것의 개수이므로 즉 A2(2개짜리의 개수)가 된다...
사실 이 사실은 5개짜리를 만들어 볼 때 깨달았다.

그래서 식은 An = An-1 + An-2가 되는 것 같다. 근데 아직 문제를 안 풀어서 한 번 풀어봐야겠다.

정답이다... 열심히 하자!