백준 1003번: 피보나치 함수 C++ Code

 dp문제는 탐색으로 푸는 것도 가능하다. 다만 값들을 저장해놓는다는 점에서 시간효율이 우수하다. 또한 데이터 간의 연결을 표현하는 점화식 풀이에도 자주 사용된다. 때문에 dp의 대표적인 예가 피보나찌인 이유가 여기에 있다.

 

 i번 째 피보나찌 수열이 가지고 있는 0과 1의 개수는 i-1번 째와 i-2번 째를 더한 수와 같다 따라서 pair형태의 배열을 통해 단순 피보나치 연산을 했다.