[백준 1003] 피보나치 함수 (자바)

백준 1003번 피보나치 함수 (자바)

 

 

 

출처

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

 

 

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

 

 

 

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

 

 

 

입출력 예

 

 

 

접근 방법

기존과 같은 재귀 방식으로 풀면 시간 초과가 나는 유형이다.(제한시간 0.25초)

시간을 줄이기 위해 DP 로 접근해야 한다.

2차원 배열을 만들어 열 부분이 0이면 0을 호출하는 개수, 1이면 1을 호출하는 개수를 보여준다.

 

점화식은 피보나치 규칙을 사용해 dp[i] = dp[i-2] + dp[i-1]이다.

하지만 연산 결괏값을 보여주는 것이 아니기 때문에 추가적인 조건이 붙는다.

 

1. i == 0인 경우에는 0이 1번, i == 1인 경우에는 1이 1번 필요하기 때문에 초기값으로 넣어준다.

 

2. i가 1이하인 경우는 초기화한 값을 그대로 넣어주고, 2 이상인 경우는 점화식을 바탕으로 열이 0인 경우와 열이 1인 경우 동일한 식을 사용하여 개수를 넣어준다.

 

3. 개수를 구함과 동시에 나중에 한 번에 출력하기 위해 출력을 위한 배열에 넣어준다.

 

 

 

내 코드

package dynamicprogramming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class PivonachiFunction {
	/**
	 * 백준 1003 피보나치 함수 (https://www.acmicpc.net/problem/1003)
	 * 보텀업 방식 사용
	 */
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(reader.readLine());
		
		int[][] dp = new int[41][2];
		int[][] result = new int[n][2]; //0개수, 1개수 담을 배열
		
		dp[0][0] = 1; //0일때 0은 1개
		dp[1][1] = 1; //1일때 1은 1개
		
		int input = 0;
		for (int i=0; i<n; i++) {
			input = Integer.parseInt(reader.readLine());
			
			if (input <= 1) {
				result[i][0] = dp[input][0];
				result[i][1] = dp[input][1];
			} else {
				for (int j=2; j<=input; j++) {
					dp[j][0] = dp[j-2][0] + dp[j-1][0]; //-2번째 0의 개수와 -1번째 0의 개수를 더함
					dp[j][1] = dp[j-2][1] + dp[j-1][1]; //-2번째 1의 개수와 -1번째 1의 개수를 더함
				}
				result[i][0] = dp[input][0];
				result[i][1] = dp[input][1];
			}
			
		}//for
		
		for (int i=0; i<n; i++) {
			System.out.println(result[i][0] + " " + result[i][1]);
		}
		
	}//main
}

 

 

 

고려할 점

1. 기존 피보나치 규칙 사용할 것

2. 2차원 배열로 0과 1 호출 개수를 분리할 것