개발자의시작

문제링크 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 문제를 보자마자 딱 DP로 풀어야 할 것 같은 감이 드는 문제입니다. 반복 또는 재귀로 피보나치 함수를 구현하는 문제는 많이들 해보셨을 것 같습니다. 이 문제는 그중에서도 피보나치 함수의 재귀 호출 횟수를 계산하는 문제입니다. 피보나치 함수의 재귀 호출 자체가 DP가 되겠네요. 먼저 아래에 문제의 경우의 수를 표현해 보겠습니다. 인자가 0인 경우와 1인 경우는 미리 갖고 있는 것으로 가정하며, 맨 오른쪽 항에 있는 리스트 안에 숫자는 각각 Fibonacci(0)을 호출하는 ..