백준 1003 - 피보나치 함수 ( Java )

wrote by : besforyou

 

 

문제 해설

 

 

n이 주어지고, 위 피보나치 함수를 실행했을때 0과 1이 반환되는 횟수를 출력하는 문제입니다.

단순히 위 함수를 실행해서 반환되는 0과 1의 횟수를 직접 구하는 알고리즘은 시간 초과가 뜹니다.

그래서 dp를 적용하여 문제를 해결해야합니다.

 

 

문제풀이

 

fibonacci(0)은 0을 1번, 1을 0번 반환하고     ---- (a)

fibonacci(1)은 0을 0번, 1을 1번 반환합니다. ---- (b)

fibonacci(2)는 fibonacci(1) + fibonacci(0)을 반환합니다. 그러므로 0을 1번, 1을 1번 반환합니다. ( a + b )

 

위를 통해서, n이 주어졌을때 0과 1이 반환되는 횟수는 함수에 n-1이 주어졌을때 반환한 0과 1의 개수와 함수에 n-2이 주어졌을때 반환한 0과 1의 개수를 더하면 구할 수 있음을 알 수 있습니다.

 

- 점화식으로 표현하면 dp[i] = dp[i-1] + dp[i-2]

 

- 단, 0과 1은 겹치지 않으므로 2개의 배열에서 따로 계산하여야합니다.

 

 

코드 

 

import java.io.*;
 
public class Main {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = 40;
        int dp[][] = new int[N+1][2];
 
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;
        dp[2][0] = 1;
        dp[2][1] = 1;
 
        for (int i = 3 ; i <= N ; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-2][0];
            dp[i][1] = dp[i-1][1] + dp[i-2][1];
        }
 
        int T = Integer.parseInt(br.readLine());
 
        for (int i = 0 ; i < T ; i++) {
            N = Integer.parseInt(br.readLine());
            System.out.println(dp[N][0] + " " + dp[N][1]);
        }
 
    }
}

 

 

결과