[백준 1003] 피보나치 함수

0. 제목

• 백준 1003 피보나치 함수
• BOJ 1003 피보나치 함수
• C++ 1003 피보나치 함수

---

1. 문제

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

---

2. 풀이

• dp방식을 사용하였다.
• dp[i][0]은 i 번째 수 계산 시 나오는 0의 개수이고 dp[i][1]은 1의 개수이다.
• i가 0, 1일때 초기값을 지정해주고 dp[i][k] = dp[i-1][k] + dp[i-2][k] 를 수행해주면 0과 1의 개수를 구할 수 있다.

---

3. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int T, N;
    int dp[41][2] = {0};
    
    cin >> T;
    
    dp[0][0] = 1;
    dp[0][1] = 0;
    dp[1][0] = 0;
    dp[1][1] = 1;
    for(int i = 0; i < T; i++){
        cin >> N;
        for(int j = 2; j <= N; j++){
            dp[j][0] = dp[j-1][0] + dp[j-2][0];
            dp[j][1] = dp[j-1][1] + dp[j-2][1];
        }
        cout << dp[N][0] << ' ' << dp[N][1] << '\n';
    }
    return 0;
}