1003번
-
1003번정리 2021. 7. 15. 21:14
f(0) = 1, f(1) = 1을 반환합니다. 먼저 ( x , y ) 를 x = 0의 출현, y = 1의 출현을 맵핑한 notation으로 쓰겠습니다. 예시에서 f(3) = f(2) + f(1) = { f(1) + f(0) } + f(1) = 1 + 0 + 1 -> (1, 2) 그렇다면 f(4) = f(3) + f(2) = { f(2) + f (1) } + { f(1) + f(0) }= [ { f(1) + f(0) } + f(1) ] + { f(1) + f(0) } = 1 + 0 + 1 + 1 + 0 -> ( 2, 3 ) 직감적으로 피보나치 수를 계산하라는 느낌이 옵니다. 그러나 그림을 통해 조금 더 확신을 갖고 어떤 점에서 동적 계획법을 활용하면 좋은지 확인해보는 것도 좋습니다. f(2)의 결과값이 ..