백준 | 1003. 피보나치 함수

 

아무래도 피보나치 자체가 이전에 했던 계산들을 반복해서 사용하는 패턴이다보니까

문제에서 요구하는 0이랑 1 개수도 패턴이 있을거같아서

이거 먼저 정리해봤음.

 

숫자	0 횟수	1 횟수
0	1	0
1	0	1

0이랑 1은 우선 정리하고 시작하고, 여기서부터 시작했을 때

이렇게 되니까

숫자	0 횟수	1 횟수
0	1	0
1	0	1
2	1	1	2 -> 1,0
3	1	2	3 -> 2(1,0) , 1
4	2	3	4 -> 3( 2(1,0) , 1), 2(1,0)
5	3	5	5-> 4( 3( 2(1,0) , 1), 2(1,0) ), 3( 2(1,0) , 1)

 

2는 1과 0의 0,1횟수를 더한거,

3은 2와 1의 0,1횟수를 더한거

4는 3+2, 5는 4+3 이런식이다.

 

이걸 활용해서 풀어보면 될거같다.

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

int main(){
    int T, n;
    cin >> T;
    vector<vector<int>>v(41,vector<int>(2));
    v[0] = {1, 0}, v[1] = {0, 1};
    for(int i = 2; i<41; ++i){
        v[i][0] = v[i-1][0] + v[i-2][0];
        v[i][1] = v[i-1][1] + v[i-2][1];
    }
    
    while(T--){
        cin >> n;
        cout << v[n][0] << " " << v[n][1] << endl;
    }
}

 

n이 40까지라고 제한을 줬으니까

0~40까지 미리 구해놓고 하면 편하다!

 

원샷 원킬!