BOJ01003 피보나치 함수

https://www.acmicpc.net/problem/1003 (opens new window)

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);
    }
}

fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구한다.

제출 코드

i인 숫자를 만들기 위해서 사용된 0과 1의 개수를 bottom-up 방식으로 dp 테이블에 저장한다.

dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
dp[i][1] = dp[i - 1][1] + dp[i - 2][1];

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ1003 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[][] dp = new int[41][2];

        int t = scanner.nextInt();

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

        for (int i = 0; i < t; i++) {
            int n = scanner.nextInt();
            System.out.println(dp[n][0] + " " + dp[n][1]);
        }
    }
}

#algorithm #BOJ #다이나믹 프로그래밍