[재귀함수/DP] BAEKJOON '2747'번 '피보나치 수 '문제 (C++/python)

문제 : www.acmicpc.net/problem/2747

2747번: 피보나치 수

 

• 문제 해결 아이디어

 

    1.  일반 recursion을 사용하면 시간 초과가 나기 떄문에, 다른 방법을 사용한다.

 

 

• python

n = int(input())

a, b = 0, 1

while n:
    a, b = b, a+b
    n -=1

print(a)

 

단순 반복문으로 값을 더해 원하는 번째의 수를 출력한다.

 

 

 

• c++

#include "iostream"

using namespace std;

int dp[46]={0,};

void fibo(int num){
    if(num == 0)
        dp[0] = 0;
    
    else if(num == 1)
        dp[1] = 1;
    
    else{
        if(dp[num-1] == 0)
            fibo(num-1);
        if(dp[num-2] == 0)
            fibo(num-2);
        dp[num] = dp[num-1] + dp[num-2];
    }
}

int main(){
    
    int num;
    scanf("%d",&num);
    fibo(num);
    printf("%d\n",dp[num]);
    
    return 0;
}

 

dp(dynamic programming)를 이용해서 문제를 해결한다.

 

dp는 간단히 말하면 이미 계산한 값들을 저장해놓고, 여러번 계산을 수행하지 않도록 하는 것이다.