[백준 JAVA]1003 피보나치 함수

import java.util.Scanner;

public class Main {
	//피보나치수
	private static long dp[] = new long[41];

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int t = scanner.nextInt();
		dp[0] = 0;
		dp[1] = 1;
		
		//t번반복
		for (int i = 0; i < t; i++) {
			//n을읽어들여서 계산.
			int n = scanner.nextInt();
			
			//만약 n == 0 이면 n-1이음수가나오므로..
			if (n - 1 >= 0) {
				System.out.println(fibonacci(n-1) + " " + fibonacci(n));
			}else {
				System.out.println("1 0");
			}
		}
		scanner.close();
	}
	//결과값을 리턴함.
	private static long fibonacci(int n) {
		if(n == 0) 
			return 0;
		
		if(n == 1) 
			return 1;
		
		
		if(dp[n] == 0) {
			return dp[n] = fibonacci(n-1) + fibonacci(n-2);
		}else {
			return dp[n];
		}
		
	}

}

포인트. 이분적으로 0과 1의 케이스를 각각 담아낼거라고 생각하지말고
0과1모두 하나의 함수에서 처리되면 당연히
그함수를 통한 새로운 점화식에서 두값이 연관되있음을 생각하자.

처음에 dp를 따로생각해내다가
다시한번 fibonacci(0)~fibonacci(6)까지 전부나타내보다가 0과 1의갯수를새보니
fibonacci(i) 는 i일때의 1의갯수, fibonacci(i-1) 는 i일때의 0 의 갯수였다.

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

좋은 웹페이지 즐겨찾기