(Baekjoon) dp - (4) 피보나치

https://www.acmicpc.net/problem/2747

2747번: 피보나치 수

dp문제의 가장 기본이 되는 피보나치이다.

점화식을 재귀함수로 어떤식으로 표현할수있느냐도 알수있는 핵심문제이다.

 

A(n) = A(n-2) + A(n-1) 의 점화식이 있을경우

 

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

 

다음과 같은 재귀함수로 구할수 있다.

하지만 한번구한값은 다시 구하지 말자 의 동적계획법을 사용하지 않을경우 시간이 너무 많이 소요된다.

 

다음과 같이 메모리에 값을 저장하고 값이 존재한다면 더이상 계산하지 않는 식으로 계산시간을 단축할수있다.

package dp;

import java.util.Arrays;
import java.util.Scanner;

public class _1003{

    static int pibo_mem[] = new int[100];
    public static int pibo(int n){

        if( pibo_mem[n] != -1) 
          return pibo_mem[n];
          
        if( n < 2 )
          pibo_mem[n] = n;
        else
          pibo_mem[n] = pibo(n-1) + pibo(n-2);

        return pibo_mem[n];

    }
    public static void main(String args[]){
        Arrays.fill(pibo_mem, -1);
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        System.out.println(pibo(a));

    }
}

 

 

 

 

 

 

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study