문제

풀이

먼저 이문제는 점화식을 도출해내서 dp로 풀어 내면 될 듯하여 dp[i]를 i자리수까지 만들 수 있는 수열의 개수로 본다면
먼저 dp[1]은 1이되고, dp[2] = 2가되는데

dp[i]를 생각 해 본다면
i자리 수의 수열을 만든다면 i번째 숫자는 먼저 1이나 0이 될 것이고
1일 경우에는 i-1자리 까지의 수열에 1만 더하면 되므로
0일 경우에는 i-2자리 까지의 수열에 00을 추가한 경우만 가능하므로

i자리가 1일 경우에는 dp[i]= dp[i-1]이된다
i자리가 0일 경우에는 dp[i]= dp[i-2]이되고

따라서 점화식은

dp[i] = dp[i-1] + dp[i-2]가 된다.

코드

#입력 (1 ≤ N ≤ 1,000,000) 범위의 정수 N
#출력 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

dp = [0] * 1000001
dp[0] = 1
dp[1] = 1

N = int(input())

for i in range(2, N+1):
  dp[i] = (dp[i-2] + dp[i-1]) % 15746


print(dp[N])