100년 뒤 개발자 한승규입니다.

https://www.acmicpc.net/problem/2193

일단 동적프로그래밍이다.

조건으로 N이 90까지 주어지는 데, 이거를 직접 10 ** N 이렇게 구하는 건 말도 안된다는 것은 바로 알 수 있었다.

그러고는 예시를 먼저 보자.

1로 끝나는 수 뒤에는 1이 오지 못하고 0만 올 수 있다.

하지만 0으로 끝나는 수 뒤에는 1과 0이 다 올 수 있다.

그러면 N+1에서 1로 끝나는 수의 숫자는 N에서 0으로 끝나는 수의 숫자 일 것이고, 0으로 끝나는 수의 숫자는 N에서 0으로 끝나는 수와 1로 끝나는 수의 합 일 것이다.

이 생각을 바탕으로 N=1일 때의 값은 넣어주고, 입력값 N의 답을 얻을 수 있도록 하였다.

import sys

N = int(sys.stdin.readline())

end_zero = 0
end_one = 1

for i in range(N-1):
    end_zero, end_one = end_zero + end_one, end_zero

print(end_zero + end_one)