#백준 1904번 #파이썬 #문제풀이

### 문제설명 

- 1,0 을 주어진 n자리에 각각 할당할 수 있는 수열의 경우의 수를 구하여라. 

- 제한조건: 1은 단독으로 사용 가능. 0은 단독으로 사용불가능. 따라서 00 과 같이 연속된 0으로만 사용가능. 

- 예시) n = 2 면은 [11, 00] 의 경우가 성립. 10, 01은 성립할 수 없음.  

 

### 문제풀이

n=1  , [1] 1

n=2  , [11, 00] 2 

n=3  , [111,100, 001 ] 3

n=4  , [1111, 1100, 1001, 0000, 0011] 5    

 

- 4번을 만드는 요령은, n=3 일때의 요소 앞에 1 이 붙었을 경우, 뒤에 00이 붙었을 경우를 가정해서

중복수를 지워주면 된다.  

# Solution
import sys input = sys.stdin.readline 
n = int(input()) 
dp = [0] * 1000001 
dp[1] = 1 
dp[2] = 2

for k in range(3,n+1): 
  dp[k] = (dp[k-1] + dp[k-2])%15746 

print(dp[n])

### Comment 

- 결과값 n이 피보나치 수열을 이룸.