[boj] (b1) 2748 피보나치 수 2
✅ DP ✅ Bottom Up ✅ long long 형
문제
풀이
1. 문제 접근 및 해결 로직
- 초기값
- 점화식
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;
}
🔥 자료형 에러
- 초기값
- 점화식
#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. 시간 복잡도 분석
모든 피보나치수를 구하므로
5. 문제에서 중요한 부분
DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항
Author And Source
이 문제에 관하여([boj] (b1) 2748 피보나치 수 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@peanut_/boj-b1-2748-피보나치-수-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)