문제 출처

단계별로 풀어보기 > 동적 계획법 1 > 알고리즘 수업 피보나치 수 1
https://www.acmicpc.net/problem/24416

문제 설명

재귀로 구현한 피보나치와 동적 프로그래밍을 이용한 피보나치에 각각 코드 1,2가 얼마나 호출 되었는지 확인하라.

접근 방법

문제에서 재귀와 동적프로그래밍을 이용한 sudo 코드를 주었으므로, 이를 이용하여 구현한다. 코드1의 경우 1을 return할 때, 횟수를 증가시키고, 코드 2는 반복문 만큼 증가 시킨다.

import java.io.*;

public class 알고리즘_수업_피보나치_수_1 {

    public static int f[] = new int[40];
    public static int code1 = 0;
    public static int code2 = 0;

    public static int fib(int n){
        if(n==1 || n == 2){
            code1++;
            return 1;
        }

        return fib(n-1) + fib(n-2);
    }

    public static int fibonacci(int n){
        for(int i = 2; i<n; i++){
            code2++;
            f[i] = f[i-1] + f[i-2];
        }
        return code2;
    }

    public static void main(String[] args) throws IOException {
        f[0] = 1;
        f[1] = 1;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        fib(N);
        fibonacci(N);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(code1)+ "\n");
        bw.write(String.valueOf(code2));
        bw.flush();
        bw.close();
        br.close();
    }
}

Review

import java.io.*;

public class 알고리즘_수업_피보나치_수_1_reivew {

    public static int code1 = 0;
    public static int code2 = 0;

    public static int fib(int n){
        if ( n == 1 || n == 2 ){
            code1++;
            return 1;
        }
        return fib(n-1) + fib(n - 2);
    }

    public static int fibonacci(int n){
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 1;

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

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

        int N = Integer.parseInt(br.readLine());

        fib(N);
        fibonacci(N);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(code1 + " " + code2);
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

문제를 제대로 안 읽어서 코드1, 코드2가 명확하게 보지 않고 풀었다.
문제를 제대로 읽자.

문제푼 흔적

Review