프로그래머스, 피보나치 수 : C++ [CPP]

DP의 개념이 있고

Memoization의 개념이 있어야 한다.

 

https://programmers.co.kr/learn/courses/30/lessons/12945?language=cpp 

 

---

 

#배운 점

Memoization과

하위 문제로 나눌 수 있는지 DP 풀이

계산된 결과를 저장하고 바로 불러올 수 있는가?

 

---

 

 

# 맞는 풀이

#include <string>
#include <vector>

using namespace std;

/*
//재귀로 구현한 피보나치 (memoization x)
int func(int n){
    if(n == 0)return 0;
    if(n == 1) return 1;
    return (func(n-1) + func(n-2)) % 1234567;
}
*/

//for memoization
int arr[100001] = {0};


//해당 배열에 값이 저장 안되어있으면 계산해서 저장하고
//해당 배열에 값이 저장 되어있으면 바로 꺼낸다.
int func(int n){
    if(n == 0) return arr[0]; // 기본 - 1
    if(n == 1){ // 기본 - 2
        if(arr[1] == 0){
            arr[1] = 1;
        }
        return arr[1];
    }
    //n번째 배열이 비어있다면
    if(arr[n] == 0){
        //이전의 결과에서 계산해서 저장함.
        arr[n] = (func(n-1) + func(n-2))%1234567;
        return arr[n];
    }else{
        //이미 계산되어있다면 바로 불러냄.
        return arr[n];
    }
}



int solution(int n) {
    int answer = 0;
    answer = func(n);
    return answer;
}