나의 풀이
import sys
input = sys.stdin.readline
n=int(input())
dp=[[0,0] for _ in range(n+1)]
dp[1][1]=1
for i in range(2,n+1):
dp[i][0]=dp[i-1][0]+dp[i-1][1]
dp[i][1]=dp[i-1][0]
print(sum(dp[n]))수행시간: 68ms
풀이
dp[i]에는 i자리 이친수를 [0으로 끝나는 이친수의 수,1로 끝나는 이친수의 수] 형태로 저장한다.
i자리 이친수 중 0으로 끝나는 이친수의 수는 i-1자리 이친수 중 0으로 끝나는 이친수 + i-1자리 이친수 중 1로 끝나는 이친수 이다.
1로 끝나는 이친수의 수는 i-1자리 이친수 중 0으로 끝나느 이친수의 개수이다.
