위와 같이 피보나치수열을 계산할 때 0이랑 1이 출력되는 횟수를 구하는 문제.
문제 그대로 재귀로 풀려고 하니 당연히 시간 초과가 났었다.
피보나치수열 계산하는 것부터 O(2^n)인데 그걸 t번... 당연히 0.25초만에 결과가 나오지 않았다.
그렇지만 사실 나는 다이나믹 프로그래밍 경험이 전무해서 이외의 방법이 전혀 떠오르지 않았고 1시간을 넘게 고민하게 돼서 바로 찾아보았다.
참고 블로그 : https://bio-info.tistory.com/122
위 블로그에서는 0이 출력되는 횟수, 1이 출력되는 횟수를 계속해서 더해서 구하는 방법을 택하였다.
N이 0일 때는 0은 1번 1일 때는 0번 출력되고 N이 1일 때는 0은 0번 출력, 1은 1번 출력 되고 이후에는 피보나치수열대로 출력되는 횟수를 쌓아서 저장하는 거다.
위 블로그에서의 코드가 왜 같은 결과를 가지는지 이해하고 그대로 작성하였으나 다이나믹 프로그래밍이 뭔지에 대해서는 감을 아예 못 잡고 있기 때문에... 그 부분 관련해서는 공부를 해보아야 할 것 같다.
