01타일 - 1904

Seongjin Jo·2023년 5월 14일
0

Baekjoon

목록 보기
24/51

문제

풀이

import java.util.Scanner;

public class ex1904 {

    public static int[] dp = new int[1000001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;

        // -1 로 초기화
        for(int i = 3; i < dp.length; i++) {
            dp[i] = -1;
        }
        System.out.println(fibo(n));
    }

    public static int fibo(int n) {
        // 계산되어있지 않는 부분만 호출 , 메모이제이션
        // fibo(4)를 호출하게 되면 fibo(2)가 2번호출되는것을 1번만 호출하기 위함.
        if(dp[n] == -1) {
            dp[n] = (fibo(n - 1) + fibo((n - 2))) % 15746;
        }
        return dp[n];
    }

}

이 문제는 쉬워보여도 굉장히 까다로운 문제다. 우선 n값의 범위는 100만 까지 주어진다.
그리고 하나 배운 점

  • dp = new int[n+1]; 이렇게 선언하면 미리 dp[0],dp[1],dp[2] 등에 값을 선언해두면 배열 할당문제가 발생한다. 이거 몰라서 한참 헤맸네;;;; ㅋㅋㅋ 그래서 결국 전역으로 직접 선언해줬다.

메모이제이션

이 문제의 규칙을 찾다보면 피보나치와 같은 규칙이라는 것을 쉽게 알 수 있다. 그래서 쉬워보였다.... 여기서 핵심은 메모이제이션이다. 예를 들어 fibo(4)를 호출한다고 하자. 그러면 fibo(3) + fibo(2)를 호출하게 되는데 fibo(3)은 또 다시 fibo(1)과 fibo(2)를 호출하게 되므로 fibo(2)를 2번 호출하게된다. 굉장히 비효율적이다. 그래서 조건을 걸어서 초기화되어있던 값이 아닌경우에는 fibo()를 호출하지 않는다.

0개의 댓글