[Algorithm] Baekjoon 1003번 : 피보나치 함수

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

1003번: 피보나치 함수

int zeroCount = 0;
int oneCount = 0;
pair<int, int> pArray[41];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n = 0;
    int temp = 0;
 
    pArray[0] = {1,0};
    pArray[1] = {0,1};
    
    for (int i = 2; i <= 40; i++)
    {
        pArray[i].first = pArray[i - 1].first + pArray[i - 2].first;
        pArray[i].second = pArray[i - 1].second + pArray[i - 2].second;
    }
    
    vector<int> iv;
    cin >> n;
    
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        iv.push_back(temp);
    }
 
    for (int i = 0; i < iv.size(); i++)
    {
        cout << pArray[iv[i]].first << ' ' << pArray[iv[i]].second;
        cout << endl;
    }
    
    return 0;
}

 

입력된 피보나치수에 대해 0과 1이 얼마나 호출되는지 묻는 문제이다..

문제 예시에 피보나치함수가 있긴한데 당연히 그거 그대로 쓰면 시간초과나고, DP 바텀탑으로 미리 값 기록해놓는 방식을 써야한다.

0과 1호출카운트를 pair로 해서 40까지 값 기록한다음 그대로 출력시키니 당연히 통과는 된다.

 

찾아보니까 규칙이 있기도 하다.

일반 피보나치처럼 값을 구해놓은 다음 ( dp[i] = dp[i-1] + dp[i-2] ), 0의 카운트는 dp[n-1]을 리턴하면되고 1의 카운트는 dp[n]을 리턴하면 된다.