백준 2748번: 피보나치 수2

 

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

 

메모리 제약 사항이 128 MB 임으로 메모제이션이나 다이나믹프로그래밍으로 접근 해야 한다.

키워드 - 정수론, 피보나치, 다이나믹 프로그래밍

 

1 2 3 5 8 13 21 이전 요소의 값을 계속 더해 준다

 

Source

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>         // greater 사용 위해 필요  
#include <string>

using namespace std;

// 자료형 범위 명심
long long dp[91] = {0, };
int main() {
    ios::sync_with_stdio(false); cin.tie(0);  // scanf 안쓸 경우 쓰세요. Cin 사용시

    dp[1] = 1;
    dp[2] = 1;

    for(int i = 3; i<91; i++) {
        dp[i] = dp[i-2] + dp[i-1];
    }


    int n = 0; cin >> n;

    cout << dp[n] << "\n";
    return 0;
}