[백준,BOJ 1003] 피보나치 함수(JAVA 구현)

-내 생각

  처음에는 문제에서 주어진 피보나치 함수를 이용해 static 변수를 선언하여 0과 1에 도착할 때 마다 카운트를 해주어 출력방식을 사용하였는데, 오답처리를 받았고 또, 메모이제이션 기법을 사용하지 않아 시간초과 처리도 받았었다. 그래서 다른 분들의 글을 참고하였는데... 너무 어려웠다..

 

-해법

  이 문제는 시간초과 문제를 해결하기 위해선 문제가 요구하는 알고리즘 형태는 점화식을 세워 수식의 형태로 해결하는 것이다. 그러나 점화식을 세우는 것에 익숙하지 않았기 때문에 다른 분들의 글을 참고했는데, 한 가지 점화식을 알 수 있었다.

 

  메모리의 형태는 무엇을 사용하든 작성자 마음이지만, 이 문제에서 발견할 수 있는 규칙성은 0의 경우는 0: 1번, 1: 0번

1의 경우는 0: 0번, 1: 1번, 2의 경우 0: 1번, 1: 1번..... 과 같이 직접 작성하다 보면 아래의 표와 같은 규칙을 찾을 수 있다.

 

n 값	0의 횟수	1의 횟수
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5

 

  이와 같은 규칙에서 확인 할 수 있는 점화식은 n의 0의 횟수 = n-1의 0의 횟수 + n-2의 0의 횟수,  n의 1의 횟수 = n-1의 1의 횟수 + n-2의 1의 횟수이다. 필자는 해당 데이터를 2차원 배열에 저장했기 때문에 2차원 배열을 사용해 표현해보면, dp[n][0] = dp[n-1][0] + dp[n-2][0], dp[n][1] = dp[n-1][1] + dp[n-2][1]의 형태라는 것을 알 수 있다. 해당 점화식과 메모이제이션 기법을 알면 풀 수 있는 문제였다. 자세한 사항은 코드를 통해 확인하자.

 

import java.util.*;

public class Main {
	static int t,n;
	static int check[] = new int[41]; // 메모이제이션 기법을 위한 각 결과 저장 배열
	static int dp[][]; // 0과1의 횟수를 저장 할 배열
	
	
	static int fibonacci(int n) { // 문제에서 주어진 피보나치 수열 메소드를 일부 수정
	    if (n == 0) {	        
	        return 0;
	    } else if (n == 1) {
	        return 1;
	    }
        
	    if(check[n] !=0) {  // 이미 메모되어 있는 경우   	
	    	return check[n]; // 해당 메모의 내용을 반환
	    }
	    else {	// 메모되어있지 않은 경우
	    	
            // 메모 후 해당 값을 반환
	    	return check[n] = fibonacci(n-1) + fibonacci(n-2);      
	    }
	}
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		t= sc.nextInt(); // 테스트 케이스
		dp = new int [41][2]; // 0과 1의 수를 저장 할 배열
		dp[0][0]=1;dp[0][1]=0; dp[1][0]=0;dp[1][1]=1; // n이 0과 1인 경우는 미리 저장
        
		for(int i=0;i<t;i++) { // 테스트 케이스 반복
			n = sc.nextInt();
			fibonacci(n); // n을 입력받아 피보나치 수행
			
			for(int j=2;j<=n;j++) { // 0번과 1번은 미리 저장해두었으므로 2번부터 시작
				dp[j][0] = dp[j-1][0] +dp[j-2][0]; // 점화식
		    	dp[j][1] = dp[j-1][1] +dp[j-2][1];
			}
			
			System.out.println(dp[n][0]+" "+dp[n][1]); // n의 0과 1의 수를 출력

		}
		
		
		 	
		
	
		
	}
	
}

 

  글을 작성하는 과정에서 알게 된 것인데, 이 문제는 별도의 피보나치 메소드가 필요없다. 즉, 점화식만을 세워 초기 0번과 1번의 상태만을 저장하고 수행하면 정답 처리를 받을 수 있다. 그러나 학습하는 과정이므로 피보나치 메소드도 추가해 작성했다.