궤도

문제 풀이 동적계획법의 입문(?) 문제이다. 정확히 말하자면 찐 입문은 재귀 함수로 구현된 피보나치 함수를 동적계획법으로 구현하는 것인데...거의 같은 구조이다. n>1 일 때 fib(n) = fib(n-1) + fib(n-2)이다. 그렇다면 fib(n)에서 0이 호출된 횟수는? 당연히 fib(n-1)에서 0을 호출한 횟수와 fib(n-2)에서 0을 호출한 횟수를 더한 값일 것이다. 1이 호출된 횟수 역시 마찬가지일 것이고... 소스코드 #include using namespace std; void fibo_cnt(int num) { int zero_cnt[41] = { 0, }; int one_cnt[41] = { 0, }; for (int i = 0; i