[백준/C++] 알고리즘 1003번 - 피보나치 함수

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 1003번 - 피보나치 함수 를 풀어보도록 하겠습니다.

 

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

1003번: 피보나치 함수

 

[문제 접근]

n = 2, n =3 , n= 4 .... 일 때  f(0)과 f(1)이 호출된 개수를 확인하면서 패턴이 있는지 계속 생각했습니다.

D[i] = D[i-2] + D[i-1] (i >= 2) 점화식을 발견하고 for문을 이용하여 bottom-up방식으로 점화식 값들을 채웠습니다.

 

[풀이 전략]

1. d[0],d[1] 초기값을 설정합니다.

2. 점화식, for문을 이용하여 d[i]의 값들을 구합니다.

3. 최종 d[n]의 값을 출력합니다.

 

[코드]

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

int t ; 
int n ; 
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> t ;
    while (t--)
    {   
        pair<int,int> d[41];
        cin >> n ;
        d[0] = {1,0};
        d[1] = {0,1};
        for(int i = 2 ; i <= n ; i++){
            d[i] = {d[i-2].first + d[i-1].first, d[i-2].second + d[i-1].second };
        }
        cout << d[n].first << ' ' << d[n].second<<'\n' ; 
    }
}

 

[배울 점]

- i = 1, 2, 3 패턴을 찾아보고, i = k , i = k+1 ... 에서 패턴을 적용해서 성립여부 확인하기.