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

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

1int fibonacci(int n) {
2    if (n == 0) {
3        printf("0");
4        return 0;
5    } else if (n == 1) {
6        printf("1");
7        return 1;
8    } else {
9        return fibonacci(n‐1) + fibonacci(n‐2);
10    }
11}

N이 주어지고 fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5  unsigned arr[41] = {0, 1, 1, 2, 3, 5};
6  for(int i=6; i<41; ++i) 
7    arr[i] = arr[i-2] + arr[i-1];
8
9  int t;
10  cin >> t;
11  while(t--) {
12    int a;
13    cin >> a;
14    if(a==0) cout << "1 0" << endl;
15    else cout << arr[a-1] << ' ' << arr[a] << endl;
16  }
17  return 0;
18}

시간 복잡도

• 최대 입력이 M이라고 했을 때, M까지의 값을 구하는 반복문 - O(M)
• 각 테스트 케이스에서의 입출력 = T * O(1) = O(T)
• 최종 시간 복잡도: O(T*M)

공간 복잡도

• 입력이 M까지 주어지고 M까지의 값을 미리 구해놨기 때문에 O(M) 이라고 볼 수 있을 것 같다.
• 최종 공간 복잡도: O(M)