백준 24416 자바 (피보나치, DP)

문제 링크

풀이

    public class B24416 {

        static int count = 0;
        static int[] dp;
        static int dpCount = 0;


        static int fibonazzi(int n){
            if (n == 1 || n == 2){
                count++;
                return 1;
            } else return fibonazzi(n-1) + fibonazzi(n-2);
        }

        static int fibonazziDp(int n){
            dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 1;

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

            return dp[n];
        }
        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 parsedInt = Integer.parseInt(br.readLine());

            fibonazzi(parsedInt);
            fibonazziDp(parsedInt);

            bw.append(String.valueOf(count)).append(" ");
            bw.append(String.valueOf(dpCount));
            bw.flush();
            bw.close();
            br.close();
        }
    }

---

라인별 해석

1. 변수 선언

        static int count = 0;
        static int[] dp;
        static int dpCount = 0;

• 각 매서드별로 카운트를 해줘야 해서 두 개의 카운트를 나눴고, Dynamic Programming 위해서 새 배열을 선언한 후 재사용 하기로.

---

2. 재귀로 호출하는 피보나치

static int fibonazzi(int n){
            if (n == 1 || n == 2){
                count++;
                return 1;
            } else return fibonazzi(n-1) + fibonazzi(n-2);
        }

• 재귀함수를 사용한 피보나치 수열은 다음과 같이 이루어짐

f(3) = f(2)[f(2) = f(1) + f(0)] + f(1) ...

• 즉 n의 연산시에 무조건 1,2를 거친다는 결론이 나온다.
  따라서 if문의 외부가 아닌 내부에 count++ 코드를 넣어준다.

---

3. DP 이용한 피보나치

static int fibonazziDp(int n){
            dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 1;

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

            return dp[n];
        }

• DP의 Tabulation 사용해서 피보나치 수열을 푸는 부분. 실제 매서드의 호출이 재귀적으로 일어나는 것이 아니라 반복문을 사용하므로 반복문 안에 dpCount++;

---

4. 호출과 입출력

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 parsedInt = Integer.parseInt(br.readLine());

            fibonazzi(parsedInt);
            fibonazziDp(parsedInt);

            bw.append(String.valueOf(count)).append(" ");
            bw.append(String.valueOf(dpCount));
            bw.flush();
            bw.close();
            br.close();
        }

• 버퍼드 리더, 라이터 사용

---

나는 피보나치 + DP 이 흐름이 너무 맘에 든다. DP의 아이디어가 맘에듬