[코딩테스트 C++] 피보나치 함수

오늘의 문제

https://www.acmicpc.net/problem/1003

피보나치 함수

나의 풀이

#include <iostream>
#include <vector>
using namespace std;

// 피보나치 함수
int call[] = {0, 0};
void solution(int n){
    vector<pair<int, int>> dp(n+1, make_pair(0, 0));
    dp[0].first = 1;
    dp[1].second = 1;
    for(int i=2;i<=n;i++){
        dp[i].first = dp[i-1].first + dp[i-2].first;
        dp[i].second = dp[i-1].second + dp[i-2].second;
    }
    cout<<dp[n].first<<" "<<dp[n].second<<endl;
}

풀이 법

• O(N)짜리 알고리즘을 만드려면 Dp를 만들어야한다. 각 dp에 0이 참조된 횟수, 1이 참조된 횟수를 저장한다.

다른 답안

#include<stdio.h>
int a[42]={1},n,t;
int main(){
	scanf("%d",&t);
	for(int i=2;i<42;i++)a[i]=a[i-1]+a[i-2];
	for(int i=0;i<t;i++)scanf("%d",&n),printf("%d %d\n",a[n],a[n+1]);
}

배울 점

• 이 규칙성을 보면 0이 참조된 것은 이전 숫자의 값이다. 그러한 이유로 이런 답이 나온것