[프로그래머스] 프로그래머스 Level2 피보나치 수 C++

문제

https://programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

풀이

유명한 피보나치 수 문제이다. DP로 해결해 주었다.

문제에 친절하게 점화식이 나타나있어서 점화식을 따로 구할 필요도 없었다.

문제를 통해 점화식은 DP[N] = DP[N - 1] + DP[N - 2]임을 알 수 있고 F[N]을 찾을때까지 for문을 돌려주었다. for문을 돌려줄 때 1234567로 나누어주는 것을 잊지 말자.

코드

#include <string>
#include <vector>

using namespace std;

int dp[100001];

int solution(int n) {

    dp[0] = 0;
    dp[1] = 1;

    if (n == 0)
    {
        return dp[0];
    }
    else if (n == 1)
    {
        return dp[1];
    }

    for (int i = 2; i <= n; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
    }

    return dp[n];
}