[BAEKJOON/Python3] 백준 1003 피보나치 함수

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

＊링크로 접속하여 문제를 확인할 수 있습니다.

 

피보나치 수를 구하는 다음과 같은 C++ 함수가 있을 때 n번째 피보나치 수를 구하고자 하면 0과 1이 각각 몇 번 출력되는지 구하는 문제입니다.

주어진 함수를 이용하여 2번째 피보나치 수를 구하기 위해서는 fibonacci(1)과 fibonacci(0)을 호출하고, 3번째 피보나치 수를 구하기 위해서는 fibonacci(2)와 fibonacci(1)을 호출하는 방식으로 피보나치 수를 구하게 됩니다. 그렇다면 fibonacci(3)에서는 fibonacci(2)와 fibonacci(1)을 호출하는 것이며 이는 곳 fibonacci(1)을 두 번, fibonacci(0)을 한 번 호출하는 것과 동일하다고 볼 수 있습니다. 이처럼 쪼개서 작은 문제부터 해결하는 동적계획법을 이용하여 해결할 수 있습니다.

 

※동적계획법(Dynamic Programming)은 문제를 작은 문제로 쪼개서 해결하되, 작은 문제의 솔루션을 모두 테이블에 저장하고 필요할 때 읽어와 사용할 수 있도록 하는 방법입니다.

 

코드

 

테스트 케이스를 입력받고 이를 입력 받을 때 최댓값을 함께 구해놓습니다. DP는 어차피 동일한 숫자들로 이루어지므로 매 테스트 케이스마다 새로운 DP를 만들지 않고 한 번에 하나의 DP를 이용하여 모두 해결하기 위한 방법입니다. max 함수를 이용하여 testcase의 최댓값을 구하는 것과 동일한 방법이라고 할 수 있겠습니다.

DP는 0 출력횟수, 1 출력횟수의 튜플 형태로 저장할 것 입니다.

위에서 말한 것 처럼 i-1과 i-2번째 피보나치 함수를 호출하기 때문에 계속 작은 수 부터 0 출력 횟수와 1 출력 횟수를 더하는 것이 i번째 출력 횟수를 구할 수 있는 방법입니다. 이 방법에 따라 DP에 값을 튜플 형태로 넣은 뒤, DP가 완성되면 사이에 공백을 두고 출력했습니다.