3개 이상의 타일일 때 맨 뒤에 올 수 있는 타일을 00과 1로 생각하시면 편합니다.

1 - 1

2 - 11

     00

3 - 1 00

     11 1

     00 1

4 - 11 00

     00 00

     1 00 1

     1 11 1

     00 1 1

저도 점화식 도출을 못해서 단순하게 숫자 적으면서 숫자들 사이의 규칙을 느낌적으로 맞추면서 풉니다..

00 타일은 2칸 이전의 상태를 전이하고

1 타일은 1칸 이전의 상태를 전이하므로

00타일에 대한 식 dp[i] = dp[i-2]

1타일에 대한 식 dp[i] = dp[i-1]을 결합하여

dp[i] = dp[i-1] + dp[i-2]가 됩니다.

@shg9411, @201812106

맨 뒤에 올 수 있는 타일을 기준으로 생각을 하면 편하다 라고 말씀해주셨는데

이 생각이 직관적으로 드신건가요? 맨 뒤의 타일만 보자라는 생각이 드는 것 자체가 문제를 해결하냐 못하냐같아서..

저는 말씀드렸듯이 바로 떠오르지 않아서 dp 문제를 풀 때에는 그림을 그려가면서 푸는 편입니다.

직관적으로 생각이 떠오르는 분도 계시겠지만요.

저는 먼저 첫째 자리부터 n번째 자리까지 00 또는 1을 배치하는 모든 경우의 수를 구하는 방법을 생각했습니다.

예를들어 n이 5라고 가정할 경우,

첫째 자리에 1을 대입할 경우 남은 자리는 5-1=4가 됩니다.

두번째 자리에 00을 대입할 경우 남은 자리는 4-2=2가 됩니다.(00은 두 자리를 차지하므로)

세번째 자리에 00을 대입할 경우 남은 자리는 2-2=0이 됩니다. 

이제 남은 자리가 없으므로 1/00/00으로 배치 확정 후 하나의 경우의 수를 끝냅니다.

이런 식으로 각 자리에 1 또는 00을 배치하는 모든 경우의 수를 구해 나가면 문제의 해답을 찾을 수 있습니다.

위의 해법은 재귀함수를 이용하면 쉽게 코드로 표현할 수 있습니다.

이 때, 재귀함수의 내부를 잘 보시면 결국 f(n) = f(n-1) + f(n-2)와 같다는 것을 알 수 있습니다.

재귀함수를 이용한 해법은 너무 오래 걸리므로 대신 도출한 점화식을 이용하여 코드를 짜야 정답 처리가 됩니다.

이해하시기 편하게 재귀함수 코드를 첨부해놓았습니다. 혹시 코틀린 코드가 이해가 안되신다면, 메세지 주세요~