[11726] 2xn 타일링

✔ 2xn 타일링

[백준 11726]

문제 분석하기

2 x N 크기의 직사각형을 1 x 2 또는 2 x 1 크기의 타일로 채우는 경우의 수를 구하는 점화식 D[N]을 정의해야 함

1부터 N - 1 크기에 직사각형과 관련된 경우의 수를 모두 구해 놓았다고 가정하고 

N 바로 직전에 구해야 하는 N - 1, N - 2에서 N의 길이를 만들기 위한 경우의 수를 생각해보면

D[N] = (D[N - 1] + D[N - 2])이라는 점화식을 도출할 수 있음 

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[N]은 길이 N으로 만들 수 있는 타일의 경우의 수
2. 점화식을 구함
   • D[N] = D[N - 1] + D[N - 2]
3. 점화식으로 D 배열을 채운 후 D[N]의 값을 출력
   • D 배열을 채울 때마다 문제에서 주어진 값으로 % 연산을 수행해야 함

슈도코드 작성하기

D[N](길이가 2 x N인 직사각형이 2 x 1, 1 x 2 타일을 붙일 수 있는 경우의 수)
D[1] = 1
D[2] = 2
for(i -> 3 ~ N) {
    D[i] = D[i - 1] + D[i - 2]
    나온 결과를 10007 나머지 연산 수행하기
}
D[N]값 출력하기

코드 구현하기

/**
 * 11726) 2xn_타일링
 */
public class D087_11726 {
    static long mod = 10007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        // D[N](길이가 2 x N인 직사각형이 2 x 1, 1 x 2 타일을 붙일 수 있는 경우의 수)
        long D[] = new long[10001];
        // 길이가 2 x 1일 때 타일의 경우의 수
        D[1] = 1;
        // 길이가 2 x 2일 때 타일의 경우의 수
        D[2] = 2;
        for (int i = 3; i <= N; i++) {
            // 나온 결과를 10007 나머지 연산 수행하기
            D[i] = (D[i - 1] + D[i - 2]) % mod;
        }
        // D[N]값 출력하기
        System.out.println(D[N]);
    }
}