[동적 계획법 1] [Python] 1003번. 피보나치 함수

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

---

해결 방법

피보나치 재귀 함수에 관한 문제다.

0과 1이 호출되는 횟수 자체도 규칙이 있음을 알 수 있다.

	0	1	2	3	4	5	6	7
0	1	0	1	1	2	3	5	8
1	0	1	1	2	3	5	8	13

위와 같이 호출되는 횟수도 (n-2) + (n-1) (n≥2일 때) 규칙이 있음을 알 수 있다.

 

재귀를 이용하지 않고 dp를 통해 접근했다.

 

 

해결 과정

n = 0, 1에 대한 0과 1의 호출 횟수는 미리 선언해두고 n≥2에 대해서는 dp를 통해 해결했다.

 

최종 코드는 

 

def fibonacci(n):
    countZero = [1, 0]
    countOne = [0, 1]
    
    if n == 0:
        print(countZero[0], countOne[0])
    elif n == 1:
        print(countZero[1], countOne[1])
    else:
        for i in range(2, n+1):
            countZero.append(countZero[i-1] + countZero[i-2])
            countOne.append(countOne[i-1] + countOne[i-2])
        print(countZero[n], countOne[n])
    
def main():
    n = int(input())
    
    for _ in range(n):
        m = int(input())
        fibonacci(m)
    
if __name__ == "__main__":
    main()