[DP] 백준 11726번 - 2 x n 타일링 (Java)

문제

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

2 x 5 크기의 직사각형을 채운 한 가지 방법

 

---

 

풀이과정

이 문제 역시 DP로 풀 수 있는 문제입니다.

n = 1 일 때는 2 x 1 타일로 채우는 한 가지 방법이 있습니다.

n = 2 일 때는 2 x 1 타일 2개로 채우거나, 1 x 2 타일 2개로 채우는 방법이 있겠지요.

 

그럼 n = 3 일 때는 어떨까요?

n = 2 일 때 채웠던 방법들에 2 x 1 타일을 추가할 수 있을 것입니다.

또한, n = 1 일 때 채웠던 방법들에 1 x 2 타일 2개를 정사각형 모양으로 추가할 수 있습니다.

 

이런식으로 (n - 1) 일 때의 가짓수와 (n - 2) 일 때의 가짓수를 더하면 n일 때의 가짓수를 쉽게 구할 수 있습니다.

이를 점화식으로 표현하면 다음과 같습니다.

DP(0) = DP(1) = 1  DP(n) = DP(n-1) + DP(n-2)

 

이 때, 주의할 점이 한가지가 있습니다.

배열에 값을 저장할 때, 10007를 나눈 나머지를 저장하지 않으면 오버플로우가 발생하여 잘못된 값이 들어가게 됩니다.

(이걸로 한참 헤맸습니다ㅠㅠ)

그래서 반드시 배열의 각 원소에 값을 저장할 때, 10007로 나눈 나머지를 저장해야 합니다. (밑의 코드에서 16번째 줄을 참고해주세요)

---

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int num = Integer.parseInt(br.readLine());
        int[] cases = new int[num + 1];
 
        cases[0] = 1;
        cases[1] = 1;
 
        for (int i = 2; i < num + 1; i++) {
            cases[i] = (cases[i - 1] + cases[i - 2] % 10007);
        }
 
        System.out.println(cases[num]);
    }
}

 

---