(DP) 백준 2193번 이친수

s = [0, 1, 1]
for i in range(3, 91):
  s.append(s[i - 2] + s[i - 1])
n = int(input())
print(s[n])

1부터 차례로 경우의 수를 적어보니 s[i]는 s[i-2] + s[i-1]이라는 결과를 얻을 수 있었다.
왜 이런 결과를 얻을 수 있었을까?

이친수는 맨 앞의 자리 숫자는 무조건 1이 되어야하고 1이 연속되지 않아야하기 때문에
맨 앞자리 수 1은 고정이고 뒤에 '0'이 붙는 경우와 '01'이 붙는 경우만 해당이 된다.

예를 들어보자면
3일경우는 100, 101
4일 경우는 1000, 1010, 1001
5일 경우는 10000, 10100, 10010, 10001, 10101

이렇게 되는데 결국 i가 가질 수 있는 갯수는 i-1 끝에 0을 붙인 경우와 i-2 끝에 01붙인 경우가 된다. 그래서 s[i] = s[i-2] + s[i-1]인 경우가 성립할 수 있는 것이다.