boj 2193

문제

우선 이진수 중 다음의 특정 조건을 만족하는 경우 이친수라 하여, 해당 개수를 구하는 문제이다

1. 맨 처음 앞자리가 무조건 1로 시작해야한다
2. 연속된 1이 올 수 없다

입력 : N(1~90)
출력 : N에 대한 이친수의 수

풀이

해당 조건을 만족해야할 경우 어떤 숫자이든 시작은 1이며, 다음에 이어오는 숫자는 0이어야 하므로
10이 기본 시작임을 알 수 있다
1의 경우 1. 1개
2의 경우 10. 1개
3의 경우부터 맨 뒷 바이트인 0,1 로 2개
4의 경우 3의 해당하는 경우와 2처럼 맨 앞이 10인 경우 3개.
5의 경우 4처럼 000, 001, 010의 경우와 3처럼 100, 101이 와야함을 알 수 있었다

e[i] = e[i-1] + e[i-2]와 같은
단순 점화식 문제로 풀리는데, 내가 생각하는 이유는 다음과 같다

앞서 1과 연속되면 안되는다는 조건이 있다. i=6이라는 가정하에 생각해보면,
(10)????의 4자리 중 (10)0???는 5의 모든 케이스를 가져왔을 때 똑같이 일치한다
그러나 (10)1???는 바로 앞 ?에 1이 붙으면 안되므로, (i-2)즉 4의 케이스를 붙였을 때 연속되는 1이 아니므로 경우의 수가 일치한다

그러므로 e[i] = e[i-1] + e[i-2]의 점화식이 성립된다

e = [-1, 1, 1] + [0] * 88
n = int(input())

for i in range(3, n+1, 1):
    e[i] = e[i-1] + e[i-2]
print(e[n])