1003 - 파이썬

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

1003번: 피보나치 함수

 

---

간단한 문제인거 같은데 꽤 고민을 오래한거같다. 핵심은 동적 계획법을 활용한다는거다.

다른 블로그에 많이들 올라온 방법은 도저히 이해가 안되어서 나혼자만의 방법으로 푼거 같다

찾아보니 꽤나 많이 알려진 방법이다. 아이디어는 단순하다.

dp[0][n] = n번째 수열의 0의 개수

dp[1][n] = n번째 수열의 1의 개수

 

fib(2) = fib(1) + fib(0)

fib(3) = fib(2) + fib(1) 

        = fib(0) + fib(1) + fib(1)

fib(4) = fib(3) + fib(2)

         = fib(0) + fib(1) + fib(1) + fib(1) + fib(0)

그냥 단순하게 해당 수열의 전 수열의 개수를 세는것이 끝이다.

---

fi = [[0]*41 for _ in range(2)]

for i in range(2,41):

     fi[0][0]=fi[1][1]=1

     fi[0][1]=fi[1][0]=0

     fi[0][i] = fi[0][i-1]+fi[0][i-2]

     fi[1][i] = fi[1][i-1]+fi[1][i-2]

     

for _ in range(int(input())):

     n = int(input())

     print(fi[0][n],fi[1][n])