[Java] 알고리즘 수업 - 피보나치 수 1 [24416번]

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

• 예제 입력1

5

• 예제 출력1

5 3

• 예제 입력2

30

• 예제 출력2

832040 28

---

• 문제 접근
  • 재귀 호출 피보나치 수열과 동적 프로그래밍 피보나치 수열의 연산 횟수 계산
• 문제 해결
  • 2개의 함수를 만들어서 각각 카운팅 값을 출력

• 슈도 코드

static recursionFiboCnt
static dpFiboCnt
N (피보나치 수열의 N번째 값)
recursionFibo(N)
dpFiboCnt(N)
recursionFiboCnt 출력
dpFiboCnt 출력

recursionFibo(N){
	if(N이 1 또는 2면) {
		1 반환
		recursionFiboCnt 1증가
	}
	recursionFibo(N-1) + recursionFibo(N-2) 반환
}

dpFiboCnt(N){
	f[N+1] 배열 선언
	f[1] = 1, f[2] = 1
	for(i=3 ~ N까지 반복){
		f[i] = f[i-1] + f[i-2] 저장
		dpFiboCnt 1증가
	}
	f[N] 반환
}

• 코딩하기

static int recursionFiboCnt = 0;
static int dpFiboCnt = 0;
public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int N = scan.nextInt();
    recursionFibo(N);
    dpFibo(N);
    System.out.println(recursionFiboCnt + " " + dpFiboCnt);
}
private static int recursionFibo(int n) {
    if(n == 1 || n == 2){
        recursionFiboCnt++;
        return 1;
    }
    return recursionFibo(n-1) + recursionFibo(n - 2);
}

private static int dpFibo(int n) {
    int[] f = new int[n+1];
    f[1] = 1; f[2] = 1;
    for(int i = 3; i <= n; i++){
        f[i] = f[i-1] + f[i-2];
        dpFiboCnt++;
    }
    return f[n];
}