10031 [C] 1003: 피보나치 함수 피보나치!!하면 바로 Dynamic Programming으로 풀어야겠다는 생각이 들어야한다! 가장 대표적이면서 기본적인 DP 문제가 피보나치랑 이항계수 관련된 문제이기 때문이다 예시와 같이 피보나치 함수를 f(n)부터 구한다면 호출의 개수가 n이 조금만 증가해도 기하급수적으로 늘어난다. 그렇기 때문에 f(0)과 f(1) 부터 배열에 저장하면서 f(n)을 구해야만 효율적으로 호출할 수 있다. 이 문제에서도 n이 1,2,3...증가할 수록 호출하는 f(0)과 f(1)의 개수가 피보나치 수열의 점화식을 따른다. 그렇기 때문에 이것을 배열에 미리 저장한 후 테스트케이스가 주어지면 불러오면 되는것이다 #include int arr[500001]; int fibo_0[41]; int fibo_1[41]; int m.. 2023. 8. 3. 이전 1 다음