[백준][C++] 10870 피보나치 수 5

10870. 피보나치 수 5

10870번: 피보나치 수 5

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

DP 첫 문제! 피보나치 수열이 나왔다. 간단한 문제이지만, 입력값이 20이 최대이므로, 단순 재귀를 이용한 피보나치로는 구현이 안 될 거라 생각했다.

 

메모이제이션을 쓰는 방법도 있지만... 아무래도 DP는 과거에 구한 해를 이용하는 알고리즘이니까...

단순 for문으로 돌리는 것이 제일 맞을 거라 생각했다.

#include<iostream>
using namespace std;

int main()
{
    int len;
    int a = 0, b = 1;
    cin >> len;

    // 1 이하일 경우 
    if (len <= 1)
    {
        cout << len;
        return 0;
    }

    for (int i = 0; i < len - 1; i++)
    {
        // a => b
        // b => a+b
        int temp = b;
        b = a + b;
        a = temp;
    }

    cout << b;
}

아주 간단한 DP 문제였지만, 수열의 뜻과 문제 자체가 DP와 너무 잘 맞아서 신기했다.

 

아직 DP는 감도 안 오지만...

이렇게 차근차근 해나가면 언젠가 어려운 DP 문제도 눈 감고 풀 날이 오게 되겠지...?