기록공간

역시 동적계획법을 사용하여 푸는 문제이다. 우선 규칙을 살펴보자. 피보나치 규칙인 F(N) = F(N - 1) + F(N - 2)를 염두해두고 보자. * N이 0일때 0 호출 횟수 = 1 1 호출 횟수 = 0 * N이 1일때 0 호출 횟수 = 0 1 호출 횟수 = 1 * N이 2일때 0 호출 횟수 = (1일때 0 호출 횟수) + (0일때 0 호출 횟수) = 0 + 1 = 1 1 호출 횟수 = (1일때 1 호출 횟수) + (0일때 1 호출 횟수) = 1 + 0 = 1 * N이 3일때 0 호출 횟수 = (2일때 0 호출 횟수) + (1일때 0 호출 횟수) = 1 + 0 = 1 1 호출 횟수 = (2일때 1 호출 횟수) + (1일때 1 호출 횟수) = 1 + 1 = 2 0과 1의 호출 횟수가 필요하기 때문에 ..