✅ DP ✅ Bottom Up ✅ long long 형

문제

링크

풀이

1. 문제 접근 및 해결 로직

• 초기값
  $f(0)=0,f(1)=1$
• 점화식
  $f(n)=f(n-1)+f(n-2)$

2. 코드

- Bottom Up (반복문, 타뷸레이션)

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

long long fibo[91];

// Bottm Up
int main(){
    
    fibo[0] = 0;
    fibo[1] = 1;
    
    int n;
    cin >> n;
    
    for(int i=2;i<=n;i++){
        fibo[i] = fibo[i-1] + fibo[i-2];
    }
    
    cout << fibo[n] << "\n";

    return 0;
}

🔥 자료형 에러

처음에

int fibo[91];

로 선언하고 문제를 풀었더니 기하급수적으로 증가하는 피보나치수열의 값을 int로 다 담을 수가 없어 틀린답이 나왔다.

✅ long long 형

따라서 int보다 더 넓은 범위를 담을 수 있는 long long 형으로 대체한다.

long long fibo[91];

4. 시간 복잡도 분석

모든 피보나치수를 구하므로
$O(N)$

5. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항