Java : 백준(Baekjoon) 1003번 문제 피보나치 함수

import java.util.*;
public class question_1003 {
	
	// 전역변수
	static int zeroCount;
	static int oneCount;
	
	public static void main(String[] args) {
		
		int count, n, result;
		Scanner sc = new Scanner(System.in);	
		
		// 테스트 케이스의 개수
		count = sc.nextInt();
		// 테스트 케이스 개수만큼 n 넣는 값
		if(count > 0)
		{
			for(int i=0; i<count; i++)
			{
				n = sc.nextInt();
				if(n >=0 & n <= 40)
				{
					result = fibonacci(n);
					System.out.println(zeroCount + " " + oneCount);
					//초기화작업
					zeroCount = 0;
					oneCount = 0;
				}
			}// for
		}
	}// main
	
	public static int fibonacci(int n) {
	    if (n == 0) {
	    	zeroCount++;
	        return 0;
	    } else if (n == 1) {
	    	oneCount ++;
	        return 1;
	    } else {
	        return fibonacci(n-1) + fibonacci(n-2);
	    }
	}
}

​1000번 문제부터 순서대로 풀고 있는데 1003번 문제에서 시간초과가 나와버렸다ㅠㅠ

아무래도 처리하는 시간이 0.25초가 넘어서 그런듯하다.

변수++말고 다른 방법으로는 어떤 것이 있는지 찾아보니 배열로 이용하면 시간 내에 가능하다고 한다.

 

// java 배열 그릇 설정하는 방법
int intArray[];    //declaring array
intArray = new int[20];  // allocating memory to array

int[] intArray = new int[20]; // combining both statements in one

 

import java.util.*;
public class question_1003 {

	public static void main(String[] args) {
		
		int n, result, count;
		// 입력값을 받기 전에 40이하의 자연수 N의 결과값들 다 배열에 넣어놓기
		int[] fibo = new int[42];	
		fibo[0] = 1;
		fibo[1] = 0;

		for(int i=2; i<42; i++)
		{
			fibo[i] = fibo[i-1] + fibo[i-2];
		}// for
		
		Scanner sc = new Scanner(System.in);	
		count = sc.nextInt();
		for(int i=0; i<count; i++)
		{
			n = sc.nextInt();
			if(n >=0 & n <= 40)
			{
				System.out.printf("%d %d\n", fibo[n], fibo[n+1]);
			}
		}

	}// main
}

여기 for(int i=2, i<42; i++)문에 어떤 값을 넣고

왜 그렇게 넣은 것인지에 대해 이해를 하지 못했다면,

우리는 피보나치 규칙에 대해 조금 더 공부를 해야합니다.

 

n	0	1	2	3	4	5	6	7	8	9	10
"0"	1	0	1	1	2	3	5	8	13	21	34
"1"	0	1	1	2	3	5	8	13	21	34	55

fibo[i] = fibo[i-1] + fibo[i-2];

해당 코드는 "0"을 기준으로 만든 배열입니다.

왜? fibo[] 배열은 "0"을 기준으로 만들었을까요?

표를 보시면 알 수 있듯이 "0"과 "1"이 처음에는 다르게 보이지만

점점씩 누적한 결과값을 비교하면 "0"의 횟수와 "1"의 횟수를

나열한 결과값이 일치하는 것을 알 수 있습니다.

​

System.out.printf("%d %d\n", fibo[n], fibo[n+1]);

그렇기에 마지막으로 출력할 때는

fibo[n] "0"을 기준으로 한 값과

fiibo[n+1] "1"을 기준으로 한 값을 출력하는걸 알 수 있습니다.

배열을 사용하여 문제를 풀고 제출하니 성공!

후.. 결과값만 나온다고 해서 되는 것이 아니구나ㅠㅠ

알고리즘 어렵다

 

1003번: 피보나치 함수