acmicpc.net 피보나치 관련.

문제 카테고리 : https://www.acmicpc.net/problemset/?search=%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98

읽어볼것 : https://www.acmicpc.net/blog/view/28

몰랐던 코드.

https://www.acmicpc.net/problem/2749 , https://www.acmicpc.net/problem/11444

를 풀기위한 코드. 행렬을 사용해서 하는거라함. n번째 피보나치 수를 구하는 코드.

mod = 1000000
def gob(a,b):
    c = [[0,0],[0,0]]
    for i in xrange(2):
        for j in xrange(2):
            for k in xrange(2):
                c[i][j] += a[i][k] * b[k][j]
            c[i][j] %= mod
    return c
 
n=input()
if n<=1:
    print n
else:
    ans = [[1,0],[0,1]]
    a = [[1,1],[1,0]]
    while n>0:
        if n%2==1:
            ans = gob(ans,a)
        a = gob(a,a)
        n /= 2
    print ans[0][1]

여태까지는 dp로 아래처럼 풀었다. 나중 저장용.

n=input()#for n in xrange(45):
a=1;b=1
if n==0:
    print 0
elif n==1 or n==2:
    print 1
else:
    for i in xrange(3,91):
        c = a+b
        if n==i:
            print c
            break
        a = b
        b = c