파이문

1003. 피보나치 함수 본문

문제 풀이/BOJ

1003. 피보나치 함수

민Z 2017. 4. 3. 22:53
728x90

1003. 피보나치 함수

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



숫자를 입력받아, (피보나치 계산으로) 1과 0을 얼마나 호출하는지를 출력하는 문제이다. 케이스 범위에 따라, 이전 계산 값을 그대로 사용할 수 있게 보완하면 더 좋을듯

    public void problem1003(int n) {
        if (n == 0) {
            System.out.println("1 0");
        } else if (n == 1) {
            System.out.println("0 1");
        } else if (n == 2) {
            System.out.println("1 1");
        } else {
            int[][] dp = new int[n + 1][2];
            dp[1][0] = 0;
            dp[1][1] = 1;
            dp[2][0] = 1;
            dp[2][1] = 1;
            dp[3][0] = 1;
            dp[3][1] = 2;
            for (int i = 4; 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];
            }
            System.out.println(dp[n][0] + " " + dp[n][1]);
        }
    }

    public static void main(String[] args) {
        Main sol = new Main();
        Scanner sc = new Scanner(System.in);
        int cases = sc.nextInt();
        while (cases != 0) {
            int n = sc.nextInt();
            sol.problem1003(n);
            cases -= 1;
        }
    }
}


'문제 풀이 > BOJ' 카테고리의 다른 글

11053. 가장 긴 증가하는 부분 수열  (0) 2017.11.12
2579. 계단 오르기  (0) 2017.11.12
1149. RGB 거리  (0) 2017.04.04
1463. 1로 만들기  (0) 2017.04.03
Maximum Random Walks  (0) 2016.04.17
Comments