[백준] 1003번 : 피보나치 함수 [Java]

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

1003번: 피보나치 함수

 

---

 

 

● 문제

[백준] 1003번

 

 

● 접근 방법

문제만 보면 어려워 보이는 문제.

피보나치 수열과 0, 1 개수의 상관 관계만 찾으면 문제의 난이도는 쉬워진다.

[표 1]

그럼 여기서 0,1 과 피보나치 수열의 상관 관계를 찾아보자.

 

0의 출력횟수는 dp[n-1] 인 것이 보이는가?

1의 출력횟수는 dp[n] 을 그대로 가져왔다.

 

이 문제는 다이나믹 문제인 것이다.

 

 

 

 

● 문제 풀이

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		int T,n;
		int[] dp = new int[41];
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 1;
		
		//dp에 모든 값 넣기.
		for(int i = 3; i < 41; i++) dp[i] = dp[i-1] + dp[i-2];
		
		//입력
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		
		// 테스트 케이스
		for(int i = 0; i < T; i++) {
			//입력
			n = sc.nextInt();
			if(n == 0) System.out.println("1 0");  // 초기값이므로 고정
			else if(n == 1) System.out.println("0 1"); //  초기값이므로 고정
			else System.out.println(dp[n-1] + " " + dp[n]);
		}
	}
}