125. 24416(알고리즘 수업 - 피보나치 수 1)

import java.util.*;
import java.io.*;

class Main {
	static int fibCnt;
	static int fib2Cnt;
	static int[] memo;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		fibCnt = 0;
		fib2Cnt = 0;
		memo = new int[100];

		fib(n);
		fib2(n);
		System.out.println(fibCnt + " " + fib2Cnt);

	}

	private static int fib(int n) {
		if (n == 1 || n == 2) {
			fibCnt++;
			return 1;
		} else {
			return fib(n - 1) + fib(n - 2);
		}

	}

	private static int fib2(int n) {
		if (memo[n] > 0) {
			fib2Cnt++;
			return memo[n];
		}

		if (n <= 1) {
			memo[n] = n;
			return memo[n];
		}

		else {
			memo[n] = fib2(n - 1) + fib2(n - 2);
			return memo[n];
		}

	}

}

문제요약

재귀함수와 동적프로그래밍을 이용하여 호출횟수를 출력하라.

설명

동적프로그래밍의 개념은 아래를 참고하자.

https://smhope.tistory.com/328?category=1056187 

동적프로그래밍(Dynamic Programming)

 

주의점

Down - Top 방식을 사용하면 Top - Down 보다 cnt를 한번 더 증가 시킴.

import java.util.*;
import java.io.*;

class Main {
	static int fibCnt;
	static int fib2Cnt;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		fibCnt = 0;
		fib2Cnt = -1;

		fib(n);
		fib2(n);
		System.out.println(fibCnt + " " + fib2Cnt);

	}

	private static int fib(int n) {
		if (n == 1 || n == 2) {
			fibCnt++;
			return 1;
		} else {
			return fib(n - 1) + fib(n - 2);
		}

	}

	private static int fib2(int n) {
		if (n <= 1) {
			return n;
		}
		
		int first = 0;
		int second = 1;
		int tmp = 0;
		
		for(int i = 0 ; i < n-1; i++) {
			tmp = first + second;
			first = second;
			second = tmp;
			fib2Cnt+=1;
					
		}
		return tmp;
	}

}