[코드트리 챌린지] 3주차 DP l - subproblem을 그대로 합치면 되는 DP / 피보나치 수

 

https://www.codetree.ai/missions/2/problems/fibonacci-number/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[50];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    dp[1] = 1;
    dp[2] = 1;

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

    cout << dp[n];
}

피보나치 수열의 1,2번째 값을 미리 저장해두고 for문을 통해 dp 배열에 피보나치 수열값을 모두 채웁니다.

그 후 n번째 피보나치 수열의 값을 출력합니다.

푸는 방법은 Memoization, Tabulation 두 가지 방식이 있는데 저는 Tabulation 방식을 선호하여
그 방식 위주로 사용할 예정입니다.