[백준 2193번] 이친수

이번 문제는 이전에 풀었던 01타일 문제와 매우 유사한 문제로, 다음과 같은 조건을 만족하는 이친수의 개수를 구하는 문제이다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

이러한 패턴의 문제는 n=1 부터 차근차근 구하면서 점화식을 찾아내는 것이 핵심인데, n=1부터 차례대로 값을 구해본 결과 다음과 같은 점화식을 얻을 수 있었다.

 

dp[1] = 1, d[2] = 1

dp[n] = dp[n-1] + dp[n-2] (n>=3)

 

이러한 점화식을 도출한 후, DP 테이블에 저장하여 쉽게 풀 수 있었던 DP 문제였다 :)