[백준 1003] 피보나치 함수 [C++]

 

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

1003번: 피보나치 함수

 

 이번에도 DP문제를 가져왔습니다! 피보나치 함수 자체는 쉬운 문제지만 아무래도 0.25초라는 시간과 호출 횟수라는 점에서 전 피보나치수열 문제보다는 어려웠던 것 같습니다. 난이도도 실버 3으로 확 뛰어넘었으니까요!

 

(이전 문제) :

https://minjh1126.tistory.com/m/6

[백준 2775] 부녀회장이 될테야 [C++]

 

1. 해설

 

 우선 피보나치 수열이 뭔지 간단하게 설명하자면 

 

 fib n = fib(n - 1) + fib(n - 2)

 fib 0 = 0, fib 1 = 1

 

 입니다.  fib n-1은 fib n-2와 fib n-3을 더한 값이고, 그렇게 파고 들어가다 0이나 1이 나오면 그 값을 반환합니다. 간단하죠? 이런 방식을 재귀 형식이라고도 합니다. 이곳에서 재귀란? 함수의 값을 구하기 위하여 동일한 함수를 호출하는 방식입니다. 쉽게 말해 fib n을 구하기 위하여 fib의 함수를 다시금 호출해야하는 방식입니다. 하지만 이번 문제는 이렇게 풀 수 없습니다.왜냐? 재귀는 함수를 몇 번씩이고 호출하다 보니, 시간이 오래 걸립니다. 하지만 이번 문제는 0.5초 안에 끝내야 한다는 제약 조건이 있죠. 그래서 다른 방식으로 풀어야 합니다.

 

 

피보나치 함수 0에서부터 3까지

피보나치 호출 횟수의 결론

 

 조금 이해가 되실까요? fib 2의 0 호출 횟수를 보면 fib 1+ fib 0의 0 호출 횟수, 1 호출 횟수는 fib 1+ fib 0의 1호출 횟수입니다. fib 3의 경우도 마찬가지고, 더 그려보시면 다른 값들도 똑같이 나올 겁니다. 그럼 이걸 구현해주기만 하면 되겠죠?

 

 

코드

#include <iostream>
// pair 선언에 필요
#include <utility>
using namespace std;

// pair 배열 선언
// 입력은 40까지이므로 크기는 41
pair <int, int> arr[41];

// 피보나치 함수
// 입력값과 출력값은 없음
void fib(void){
  //초깃값 설정
  // 0은 1 0, 1은 0 1
  arr[0].first = 1; arr[0].second = 0;
  arr[1].first = 0; arr[1].second = 1;
  
  // 40까지의 값을 배열에 저장
  for(int i = 2; i <= 40; i++){
    arr[i].first = arr[i - 1].first + arr[i - 2].first;
    arr[i].second = arr[i - 1].second + arr[i - 2].second;
  }
}

int main(void){
  // 테스트 횟수 입력
  int num;
  cin >> num;
  
  // 피보나치 함수 실행
  fib();
  
  for(int i = 0; i < num; i++){
  	// 구하는 값 입력
    int n;
    cin >> n;
    
    // 출력
    // 0의 횟수 ' ' 1의 횟수
    cout << arr[n].first << ' ' << arr[n].second << '\n';
  }
}

 

 우선 설명드릴 게 바로 utility와 pair입니다. 사실 0의 횟수와 1의 횟수를 따로 선언해서 사용해도 되지만, 솔직히 귀찮잖아요? 걍 하나로 묶어버리고 싶은데? 그래서 pair을 사용했습니다. pair 배열은 2차원 배열과 유사하다고 하면 간단하게 표현할 수 있습니다. 대신 [i][j] 이렇게 사용하지 않고 첫 번째 값은 .first 두 번째 값은 .second로 사용할 수 있습니다. 그러면 배열도 하나만 선언하면 되고 대괄호 안의 숫자를 안 헷갈릴 수 있습니다. 짱 좋아요~~