[백준 11726] 2×n 타일링 (Java) - 다이나믹프로그래밍

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

2×n 타일링

문제

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

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

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

2

예제 입력 2 복사

9

예제 출력 2 복사

55

 

---

풀이

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

public class Main {
    static long mod = 10007;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long [] D = new long[N+1];
        
        if (N == 1) { // N이 1일 때는 바로 출력
            System.out.println(1);
            return;
        }

        // 이미 아는 답 넣기
        D[1] = 1;
        D[2] = 2;
        for(int i=3; i<N+1; i++){
            D[i] = (D[i-1] + D[i-2]) % mod;
        }

        System.out.println(D[N]);
    }
}

• 다이나믹 프로그래밍을 활용한 문제
• 2xn크기의 타일을 1x2크기의 타일 혹은 2x1크기의 타일로 채우는 경우의 수를 구하는 것이다.
• 즉 n을 1, 2의 조합으로 몇가지나 만들어낼 수 있는지나 다름없는 문제
• 배열D에는 2xn 크기의 타일을 채우기 위한 경우의 수를 담고 있다.
  • D[5] = 2x5크기의 타일을 1x2크기의 타일 혹은 2x1크기의 타일로 채우는 경우의 수
• 점화식을 구해보기 위해 대부분의 문제가 해결됐다고 가정해보자
  • D[n-1]까지 채워졌다고 가정해보면, 1만 채워주면 되므로 1x2 타일 하나만 들어가면 된다.
  • D[n-2]까지 채워졌다고 가정해보면, 2만 채워주면 된다.
    • 1x2크기의 타일 2개로 채워주는 방법 -> 이방법은 D[n-1]에서 이미 충족이 됐으므로 경우의 수에 더하지 않는다.
    • 2x1크기의 타일 1개로 채워주는 방법
  • 즉, 일반 점화식은 D[n] = D[n-1] + D[n-2] 이다.
• for문을 3 ~ N까지 순회하면서 일반점화식을 기반으로 배열의 값을 채워준다.
  • 10007로 나눈 결과값을 출력하라고 했으므로 점화식을 적용해줄 때 mod로 나누어서 저장해준다.
• N의 크기가 1이하일 수 도 있으므로, 만약 N이 1이라면 1을 출력하고 바로 종료한다.