알고리즘/백준

백준 2748 피보나치 수 2 c++ [컴공과고씨]

시간빌게이츠 2022. 3. 22. 23:44
반응형

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

 

2748번: 피보나치 수 2

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

피보나치 수를 구하는 문제.

문제를 보면 처음 들어야할 생각은 동적 계획법(dynamic programing)를 떠올려주면 쉽게 풀린다.

재귀로 구현하면 아마 시간초과가 걸릴것이다.

그렇기 때문에 dp 배열을 이용하여 각 값을 저장해주고 다음 값을 구할때 계산하는 대신 앞에 계산한 값을 가져와주면 된다. 현재 값은 그 전의 값 + 그 전전 값 이 식을 구현해 주면 된다.

그리고 dp배열 선언할때 int로 선언하면 범위가 초과 되기 때문에 long long으로 해주었다. 

 

전체코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    long long dp[91]; // 범위 초과 방지
    dp[0= 0;
    dp[1= 1;
    for (int i = 2; i <= n; i++){
        dp[i] = dp[i - 1+ dp[i - 2]; // 그 전 값 + 그 전전 값
    }
    cout << dp[n];
    return 0;
// dynamic programing
cs

 

사용 알고리즘 : dynamic programing(동적 계획법)

 

yea!

반응형