[12902] 3 x n 타일링

✔ 3 x n 타일링

[프로그래머스 12902]

문제 분석하기

규칙을 찾아 문제에 접근

n이 홀수일 경우 타일링이 불가능하므로 0

n이 짝수일 경우에만 타일링이 가능

1부터 n - 2 크기까지의 직사각형에 대한 타일의 경우의 수를 구했다고 가정

 

n - 2까지 타일이 채워져 있는 경우라면 가로 타일 3개로 만들 수 있는 방식 1개,

가로 타일 1개와 세로 타일 2개로 만들 수 있는 방식 2개가 존재

n - 2와 n - 4 크기 사이까지 채워져 있는 경우라면 가로 타일 3개로 만들 수 있는 방식 2개가 존재

n - 4까지 타일이 채워져 있는 경우라면 n - 2 까지 타일이 채워져 있는 경우의 수는 동일하므로 이를 제외하고

가로 타일 4개, 세로 타일 2개로 만들 수 있는 방식 2개가 존재

이때 n이 4일 때 2개, 8일 때 2개로 4의 배수마다 2개씩 발생

그러므로 아래 점화식을 사용해 D[n]을 구하도록 함

이때 n은 짝수만 가능하므로 D[n / 2]의 D 배열에 대해서 구하도록 함

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[n]은 길이 n / 2를 만들 수 있는 타일의 경우의 수
2. 점화식을 구함
3. 점화식으로 D 배열을 채운 후 D[n / 2 - 1] 값을 반환

슈도코드 작성하기

n(가로의 길이)
D(길이가 3 x n인 직사각형이 2 x 1, 1 x 2 타일을 붙일 수 있는 경우의 수)
if(n이 홀수라면)
    0 반환
else {
    D[0] = 3
    D[1] = 11
    sum(4의 배수마다 2개씩 발생하는 경우의 수에 대한 합)
    for(i -> 2부터 ~ n / 2까지) {
        sum에 D[i - 2] * 2 추가
        D[i] = D[i - 1] * 3 + 2 + sum
        나온 결과를 1000000007 나머지 연산 수행하기
    }
    D[n / 2 - 1]값 반환하기
}

코드 구현하기

/**
 * 12902) 3xn_타일링
 */
public class L006_12902 {
    // n(가로의 길이)
    public int solution(int n) {
        // D(길이가 3 x n인 직사각형이 2 x 1, 1 x 2 타일을 붙일 수 있는 경우의 수)
        // 이때 홀수는 만들 수 없으므로 짝수에 대해서만 n / 2로 배열을 만들게 됨
        long[] D = new long[n / 2];
        // n이 홀수라면
        if (n % 2 == 1)
            // 0 반환
            return 0;
        // n이 짝수라면
        else {
            // D 배열 초기화
            D[0] = 3;
            D[1] = 11;
            // sum(4의 배수마다 2개씩 발생하는 경우의 수에 대한 합)
            long sum = 0;
            // 2부터 ~ n / 2까지
            for (int i = 2; i < n / 2; i++) {
                // sum에 D[i - 2] * 2 추가
                sum += D[i - 2] * 2;
                // D[i] = D[i - 1] * 3 + 2 + sum의 결과에 1000000007 나머지 연산을 수행하여 저장
                D[i] = (D[i - 1] * 3 + 2 + sum) % 1000000007;
            }
            // D[n / 2 - 1]값 반환하기
            return (int) D[n / 2 - 1];
        }
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L006_12902 solution = new L006_12902();

        int n = 4;

        int result = solution.solution(n);

        System.out.println(result);
    }
}