[동적 계획법] 백준 11726번 2×n 타일링(Java)

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

11726번: 2×n 타일링

📚 문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

📝 문제 해결

테이블 정의

dp[N] : 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수

 

점화식 찾기

n의 크기가 증가할 때 이전 직사각형(n-1, n-2)과 연관성이 있음을 확인할 수 있다.

따라서 점화식을 유추해보면 아래와 같다.

dp[n] = dp[n-1] + dp[n-2]

 

초기값 정의

dp[1] = 1

dp[2] = 2

 

💻 코드

package BOJ;

import java.util.Scanner;
public class No11726 {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[1001];

        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=n; i++)
            dp[i] = (dp[i-1] + dp[i-2])%10007;

        System.out.println(dp[n]);
    }
}

💡  방법의 수를 10007로 나눠서 출력해야하는데 출력문에서 연산을 하면 오류(int 메모리 overflow) 가 난다.