[백준 *Java] - 2*n 타일링 (11726)

이번 문제는 2*n 타일링 백준 문제입니다.

역시나 DP 문제에 익숙하지 않아 문제를 이해하는데 오래걸렸습니다.

역시 DP 문제는 문제와 테스트케이스를 꼼꼼히 읽으며 하나씩 그려보거나? 쓰면서 하는 게 이해가 잘되는 거 같습니다.

DP 에 대해서 잘 모르신다면? 아래 링크를 타고가서 블로그 글을 읽고 오시면 좋을 거 같습니다 😊

다이나믹 프로그래밍

점화식

👆 위 그림과 같이 그려보면, 갯수가 피보나치 수열로 증가하는 게 보입니다.

피보나치 수열은  1, 1, 2, 3, 5, 8  이런 식으로 증가합니다. 그런데 지금 보이는 수는 1 2 3 5 8 로 증가를 하니 인덱스를 맞춰서 코드를 구현하면 됩니다. 

 

아래 코드는 주석을 달아 코드 설명을 해놓았습니다. 👇 

Top-down 방식으로 구현하였고, 주석에는 Bottom-up 방식이 있으니, 참고를하여도 좋을 거 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Boj_11726 {

    static int dp [];

    public static int fibo(int n) {
        // * 여기서도 10007를 나눠주지 않을 시, d[n]에 담긴 값이 틀어집니다.
        // 마지막에만 출력쪽에만  %10007 연산을 해줄 시 중간에 저장되는 값들이 int 값을 넘어서므로 오버플로우가 발생하기 때문이다.
        // Top-Bottom 방식의 단점의 예입니다..
        if(dp[n] > 0) return dp[n] %= 10007;
        if(2 > n) return dp[n] = n % 10007; // 메모이제이션 되어있는 값 가져오기.즉, 한번 거친 연산은 dp에 저장되어있어서 가져옴.
        return dp[n] = fibo(n-1) + fibo(n-2);
    }

    public static void main(String[] args) throws IOException {

        // 그림을 그려보면 피보나치 수열이다.
        // 일단 점화식은 An = An-1 + An-2 이다.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()) + 1; // 피보나치 수열 인덱싱 맞추기.
        dp = new int[N+1];

        // N은 피보나치수열의 인덱스번호이다.
        dp[0] = 0;
        dp[1] = 1;
        fibo(N);

        System.out.println(dp[N] % 10007);
    }
}


/*

// Bottom-Up 방식
        for(int i = 0; i < fibonacci.length; i++) {
            if(i == 0) fibonacci[0] = 0;
            else if(i == 1) fibonacci[1] = 1;
            else fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }

 */

 

 

혹시나 설명의 오류나 코드 오류, 코드 개선점이 있다면 댓글 꼭 남겨주시면 감사합니다 : )