이친수 - https://www.acmicpc.net/problem/2193

baekjoon2193.py

'''
푸는방법
1)1로 시작한다
2)1이 두 번연속 나타나지 않는다. 예 1100(x)

1
10
100
101
1000
1001
1010
10000
10001
10010
10100
10101
n=3일때
100은 10에서 0을 가져온다
101은 10에서 1을 가져온다

1001은 101에서 1을 가져온다
1000은 100에서 0을 가져온다
1010은 10에서 10을 가져온다

10000은 10000에서 00을 가져온다
10001은 1001에서 01을 가져온다
10010은 1010에서 10을 가져온다
10100은 100에서 100을 가져온다
10101은 101에서 101을 가져온다.
=> dp사용해도 됨

점화식으로 표현하면 
O, O, O, O, n
n이 0일 때 n-1번째는 0,1 상관없음 => d[n-1]
n이 1일 때 n-1번째는 0이어야 되므로 => d[n-2]
즉, n이 1일 때 n이 0인 값을 가져온다.
그러면 자동적으로 n=1일 때 n-2번째는 0으로 시작하게된다.

d[n] = d[n-1]+d[n-2]
'''

n = int(input()) - 1  # n은 1부터 시작하므로 -1해준다.
d = [0]*(n+1)
d[0] = 1
if n > 0:
    d[1] = 1
for i in range(2,n+1):
    d[i] = d[i-1] + d[i-2]
print(d[n])