백준|1904번|01타일

문제설명
1과 00을 이용해서 만들 수 있는 N자리 숫자의 개수를 출력하는 문제입니다.

작동 순서
1. 숫자의 자리수 N을 입력받습니다.
2. dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=5, dp[5]=8 이런식으로 숫자가 늘어나는데 피보나치 수열의 형식을 가지는 것을 알수 있습니다.(n자리 숫자의 종류는 dp[n-1]의 끝자리에 1을 더해준것과 dp[n-2]의 끝자리에 00을 더해준것들이기 때문입니다.)
3. N자리 숫자의 개수를 구하고 출력합니다.

소스코드

n = int(input())
dp = [0 for i in range(n+1)]
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
    dp[i] = (dp[i-1]+dp[i-2]) % 15746
print(dp[n], end="")