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

 

---

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

---

규칙을 찾으면 간단히 해결할 수 있는 문제이다.

 

우선 규칙은 아래와 같다.

fibo(0)은 0을 1번, 1을 0번 출력한다.

fibo(1)은 0을 0번, 1을 1번 출력한다.

그렇다면 fibo(2)는 0과 1을 몇번 출력할까?

 

fibo(2) = fibo(0) + fibo(1)이며 이것을 아래와 같이 풀어 쓸 수 있다.

fibo(2)의 0 출력 횟수 =  fibo(0)이 0을 출력한 횟수 + fibo(1)이 0을 출력한 횟수

fibo(2)의 1 출력 횟수 =  fibo(0)이 1을 출력한 횟수 + fibo(1)이 1을 출력한 횟수

 

점화식을 도출하면 다음과 같다.

i는 fibo(i)와 같으며,
dp[i][0] =fibo(i)가 0을 출력한 횟수 
dp[i][1]은 fibo(i)가 1을 출력한 횟수이다.

// 점화식
dp[i][0] = dp[i-2][0] + dp[i-1][0];
dp[i][1] = dp[i-2][1] + dp[i-1][1];

---

[Java]

import java.io.*;

public class Main
{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        while(t --> 0){
            int n = Integer.parseInt(br.readLine());
            int dp[][] = new int[41][2];

            dp[0][0] = 1; dp[0][1] = 0;
            dp[1][0] = 0; dp[1][1] = 1;

            for(int i=2; i<=n; i++){
                dp[i][0] = dp[i-2][0] + dp[i-1][0];
                dp[i][1] = dp[i-2][1] + dp[i-1][1];
            }

            bw.write(dp[n][0] + " " + dp[n][1] + "\n");

        }

        bw.flush();
    }

}

 

시간 복잡도는 O(n)이 되게 된다.