[백준 #1003] 피보나치 함수 - 파이썬(python)

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

동적계획법..

사실 동적계획법이 뭔지도 모르고 문제를 접했다.

열심히 구글링을 해서 대충 이해를 했다.

 

def fibonacci(n):
    if n==0: 
        calltime.append(0)
        return 0
    elif n==1:
        calltime.append(1)
        return 1
    else : 
        return fibonacci(n-1)+fibonacci(n-2)


N=int(input())
for i in range(N):
    calltime=[]
    a=int(input())
    fibonacci(a)
    zerocnt=calltime.count(0)
    onecnt=calltime.count(1)
    print(zerocnt,onecnt)

처음에는 이렇게 문제 그대로 피보나치 함수를 쓴다음에

0이 호출되면 0을 리스트에 추가하는 식으로 했었는데

당.연.히. 시간초과..

 

아예 함수 자체를 바꿨어야 했다..

정말 모르겠어서 풀이를 찾아볼까 하는 유혹이 있었지만

극복하고,, 동적계획법이 뭔지, 어떻게 구현하는지를 찾아서 풀었다.

 

def fibonacci(n):
    f[0]=[1,0]
    f[1]=[0,1]
    for i in range(2,n+1):
        f[i]=[f[i-1][0]+f[i-2][0],f[i-1][1]+f[i-2][1]]
    return f[n]

N=int(input())
for i in range(N):
    a=int(input())
    f=[0]*41
    calllist=fibonacci(a)
    print(calllist[0],calllist[1])

이 문제에서 중요한건 피보나치수열이나 수열의 N번째 값을 찾는것이 아니라

0과 1이 얼마나 많이 호출되었는지를 확인하는것이다.

 

그래서 f[0]은 0-1번, 1-0번 ([1,0])이렇게 하고

f[1]은 0-0번, 1-1번 ([0,1])이렇게 초기 설정을 해 주고,

그 다음 숫자부터는 같은 자리를 계속 더해주는 식으로 풀이했다.

 

예를들어서 f[2] = f[0][0](1)+f[1][0](0), f[0][1](0)+f[1][1](1) ==> [1,1]

f[3]=f[1][0](0)+f[2][0](1), f[1][1](1)+f[2][1])1) ==> [1,2]

 

이런식으로 계속 값이 축적될 수 있도록 풀이했다.

처음에 계속 그냥 하려고 하니까 index error가 떠서 

f 수열은 최댓값인 40까지 나올 수 있도록 41개의 수열로 생성했다.

>내가 이해한 동적계획법<

단일변수에 값을 계속 갱신하는 것이 아니라

여러 변수에 축적하는 방식으로 연산값을 저장한다.

그래서 이미 연산 된 값을 중복으로 또 써야 할 경우에는

처음부터 연산을 시작하지 않아도 되는 장점이 있다!

(정확한지는 모르겠음)