패턴

1 : 1 (1) 2 : 00 11 (2) 3 : 001 100 111 (3) 4 : 0000, 0011, 1001, 1100, 1111 (5) 5 : 00001, 00100, 00111, 10000, 10011, 11001, 11100, 11111 (8) N -1 -> N 할때는 앞에 1 붙여주고 N -2 -> N 할때는 앞에 00 붙여주고

개수는 피보니치 패턴이랑 일치함

리커젼으로 풀었는데 예전에 풀었던 답이 훨씬 더 깔끔하고 간단해서 당황......

내일은 정렬문제 함 풀어야겠다

import sys
sys.setrecursionlimit(10**7)
N = int(input())

stack = [0] *N
stack[0] = 1
if N != 1:
    stack[1] = 2

def fibonacci(n):
    if n < 1:
        return 0
    if stack[n-1] != 0:
        return stack[n-1]
    else:
        stack[n-1] = (fibonacci(n-1) + fibonacci(n-2)) %15746
        return stack[n-1]

print(fibonacci(N))

import sys
N = int(input())

stack = [1,2]
for i in range(2, N):
    stack.append(stack[i-1] + stack[i-2])
print(stack[-1])