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

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

2748번: 피보나치 수 2

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

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

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

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

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

 

전체코드

#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

 

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

 

yea!