[Python]동적계획법 백준 1904

   

문제

https://www.acmicpc.net/problem/1904

이 문제의 규칙을 살펴보면

n         수열

1            1

2            11,00

3            100,111,001

4            1100,0000,1001,1111,0011

5            10000,11100,00100,11001,00001,10011,11111,00111

...

n-2에 00을 붙이고 n-1에 1을 붙이면 n의 수열이 나오는것을 알수있다.

수열의 개수로 계산했을경우 f(n)=f(n-1)+f(n-2) 피보나치의 형태와 같다. 

나머지 계산이 아닌 일반적인 계산으로 1000000의 가짓수를 계산하면 컴퓨터가 멈추는 

모습을 볼수있었다....

n=int(input())
 
tail_list=[0 for _ in range(n+1)]
tail_list[1]=1
if n>1:
    tail_list[2]=2
    for i in range(3,n+1):
        tail_list[i]=(tail_list[i-1]+tail_list[i-2])%15746
 
print(tail_list[n]%15746)
 

이렇게 각 계산마다 나머지 연산을 해주어 저장해주어야 한다.