[백준/1003/실버3] 피보나치 함수

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

1003번: 피보나치 함수

 

<<풀이>>

 

우선 첫 번째 풀이다. DFS를 활용했고 두 개의 메서드를 활용해서 문제를 구했다.

 

정답을 맞췄다 !!!

 

근데, 시간초과가 났다 ㅠㅠ

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {
    static ArrayList<int[]> list = new ArrayList<>();
    static int m, z;

    static public void DFS(int x) {

        if(x == 0) m++;
        if(x == 1) z++;
        if(x > 1) {
            DFS(x - 1);
            DFS(x - 2);
        }
    }
    private ArrayList<int[]> solution(int n, int[] arr) {

        for (int i = 0; i < n; i++) {
            DFS(arr[i]);
            list.add(new int[] {m, z});
            m = 0;
            z = 0;
        }
        return list;
    }

    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        for (int[] x : T.solution(n, arr)) {
            for (int answer : x) {
                System.out.print(answer + " ");
            }
            System.out.println();
        }
    }
}

 

메모제이션 사용

보통 여기서 시간 초과가 나는 이유는 이미 구한 데이터를 또 다시 구하면서 시간을 쏟기 때문에 발생하는 것이다.

 

일반적으로 재귀함수 자체가 시간부분에서 최악인 알고리즘인데 이를 최소화 하기 위해서 메모제이션을 활용한다.

 

메모제이션을 활용할때 기본적으로 배열을 많이 사용하는데 true false로도 사용한다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {
    static ArrayList<int[]> list = new ArrayList<>();
    static int m, z;
    static int[][] ch;

    static public void DFS(int x) {

        if (ch[x][0] != 0 &&  ch[x][1] != 0) {
            m += ch[x][0];
            z += ch[x][1];
        } else {

            if (x == 0) m++;
            if (x == 1) z++;
            if (x > 1) {
                DFS(x - 1);
                DFS(x - 2);
            }
        }
    }

    private ArrayList<int[]> solution(int n, int[] arr) {

        for (int i = 0; i < n; i++) {
            DFS(arr[i]);
            list.add(new int[] {m, z});
            ch[arr[i]] = new int[] {m, z};
            m = 0;
            z = 0;
        }
        return list;
    }

    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        ch = new int[41][2];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        for (int[] x : T.solution(n, arr)) {
            for (int answer : x) {
                System.out.print(answer + " ");
            }
            System.out.println();
        }
    }
}

 

이번에 메모제이션을 활용해서 만약 이미 구한 값이라면 그 값을 불러와서 진행하는 식으로 했는데 ,, 또다시 시간초과이다 ㅋㅋㅋㅋㅋ

 

일단은 (0,0) 인 경우도 중복 계산에서 벗어나게 해줘야 한다. 그래서 ch 초기값을 -1로 바꿈으로써 할 수 있었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {
    static ArrayList<int[]> list = new ArrayList<>();
    static int m, z;
    static int[][] ch;

    static public void DFS(int x) {

        if (ch[x][0] != -1 &&  ch[x][1] != -1) {
            m += ch[x][0];
            z += ch[x][1];
        } else {

            if (x == 0) m++;
            if (x == 1) z++;
            if (x > 1) {
                DFS(x - 1);
                DFS(x - 2);
            }
        }
    }

    private ArrayList<int[]> solution(int n, int[] arr) {

        for (int i = 0; i < n; i++) {
            DFS(arr[i]);
            list.add(new int[] {m, z});
            ch[arr[i]] = new int[] {m, z};
            m = 0;
            z = 0;
        }
        return list;
    }

    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        ch = new int[41][2];
        for (int i = 0; i < 41; i++) {
            ch[i][0] = -1;
            ch[i][1] = -1;
          }
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        for (int[] x : T.solution(n, arr)) {
            for (int answer : x) {
                System.out.print(answer + " ");
            }
            System.out.println();
        }
    }
}

 

그래도 시간초과 ㅋㅋ 미치겟다 ㅋ

 

DP 활용

 

결국,,, DP를 활용해서 풀어라는 문제였다 ㅋㅋ ㅎㅎ

근데, 아직 DP에 대한 개념이 많이 없어서 공부하고 다음에는 이걸 제대로 풀어보도록 하겠다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {
    static int[][] dp = new int[41][2]; // 메모이제이션을 위한 배열

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수

        // dp 배열 초기화
        dp[0][0] = 1; dp[0][1] = 0; // fibonacci(0)은 0을 1번, 1을 0번 반환
        dp[1][0] = 0; dp[1][1] = 1; // fibonacci(1)은 0을 0번, 1을 1번 반환

        // fibonacci(2)부터 fibonacci(40)까지 계산
        for (int i = 2; i <= 40; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-2][0]; // 0 반환 횟수
            dp[i][1] = dp[i-1][1] + dp[i-2][1]; // 1 반환 횟수
        }

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            sb.append(dp[N][0]).append(' ').append(dp[N][1]).append('\n');
        }
        System.out.println(sb.toString());
    }
}

 

 

<<추가 공부>>

ArrayList 

 내가 이걸 적용하다가 좀 애를 먹었다. 그 정확한 원리? 구조? 를 몰랐다고 볼 수 있다.

ArrayList를 초기화 시키면 null 이고 0이고 없는 상태이다. 근데 특정한 인덱스에 접근하려고 하면 에러가 발생한다.

나는 이를 모르고 무작정 넣으려고 했다. 

다음 부터 이를 적용할 때에는 먼저 넣고 난 뒤 해야 한다는 것을 잊지말자!!!

 

ArrayList 메서드

set : 존재하고 있는 특정 인덱스의 값을 대체할 때 쓴다.

 

add : 존재하고 있는 특정 위치의 인덱스에 값을 넣고 원래 위치에 있던 인덱스의 값은 뒤로 미룬다. 

 

int[][] arr = new int[5][5];

이러한 배열이 있다면 초기화는 각 위치마다 초기화 0이 된다. 

 

int[][] arr = new int[5][];

이렇게 하면 arr[1], arr[2] .... 의 값은 null로 된다. 나는 이부분이 헷갈렸어서 잘못 적용을 했었다.