[백준-1003]-[다이나믹프로그래밍] - 피보나치 수열

문제링크 : https://www.acmicpc.net/problem/1003

이문제는 생각보다 쉽게 방법을 찾았다. 

다행이다.

문제에서 친절하게 C++ 피보나치 DP 소스를 제공해줬다. 하지만 이문제를 푸는데 대략적인 힌트만 줄 뿐 저 소스를 이용할 필요는 없다.

숫자 5까지의 피보나치를 계산해보면서 이 문제를 어떻게 풀어가야할지 방법을 파악해보자.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

숫자 0과 1이 들어오면 0, 1을 리턴한다고 한다.

그럼 저 둘은 기본값이겠구만 하는 똘똘한 생각을 해봤다. 

	fibonacci(n-1)	fibonacci(n-2)	출력된 0의 횟수	출력된 1의 횟수
0	--	--	1	0
1	--	--	0	1
2	1	0	1	1
3	2	1	1	2
4	3	2	2	3
5	4	3	3	5

0부터 5까지의 피보나치를 돌면서 출력된 0과 1의 횟수를 뽑아 봤다. 저기서 공통점을 찾아볼 수가 있는데

기본값인 0과 1을 제외하고 2부터는 n-1의 0과 1의 횟수와 n-2의 0과 1의 횟수의 합이 n의 0과 1의 출력 횟수라는게 보인다.

나만의 점화식을 계산해본다면

각 숫자별 0과 1의 출력 횟수를 담고 있는 정수형 이차원 배열 cnt[N+1][2] 를 생성하고 재귀를 돌면서 계산 하면 된다. 

하지만 문제에서 최대값을 40으로 지정해줬기 떄문에 40까지 계산하고 입력받는 값들의 정보만 출력하면 된다.

cnt[n][0] = cnt[n-1][0] + cnt[n-2][0]

cnt[n][1] = cnt[n-1][1] + cnt[n-2][1]

아주 쉽게 점화식을 구했으니 이제 코딩을 해보자 잘 나오겠지

import java.util.Scanner;
 
public class E_1003 {
    
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int fibo = 40;
        int[][] cnt = new int[fibo+1][2];
        
        cnt[0][0] = 1;
        cnt[1][1] = 1;
        
        for(int i=2; i <=fibo; i++) {
            cnt[i][0] = cnt[i-1][0] + cnt[i-2][0];
            cnt[i][1] = cnt[i-1][1] + cnt[i-2][1];
        }
        
        
        int num = sc.nextInt();
        
        for(int i=0; i < num; i++) {
            int n = sc.nextInt();
            System.out.println(cnt[n][0] + " " + cnt[n][1]);
        }
    }
 
}