[12900] 2 x n 타일링

✔ 2 x n 타일링

[프로그래머스 12900]

문제 분석하기

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

n - 1까지 타일이 채워져 있는 경우라면 1 x 2 크기의 타일만 사용 가능하므로 n - 1가지 만들 수 있는 타일의 경우의 수와 동일

n - 2까지 타일이 채워져 있는 경우라면 1 x 2, 2 x 1 크기의 타일이 모두 가능하지만 1 x 2의 경우는 이미 사용된 방식이므로 제외함

그러므로 D[n - 1] + D[n - 2]를 사용해 D[n]을 구하도록 함

손으로 풀어보기

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

슈도코드 작성하기

n(가로의 길이)
D(길이가 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]
    나온 결과를 1000000007 나머지 연산 수행하기
}
D[n]값 반환하기

코드 구현하기

/**
 * 12900) 2xn_타일링
 */
public class L005_12900 {
    // n(가로의 길이)
    public int solution(int n) {
        // D(길이가 2 x n인 직사각형이 2 x 1, 1 x 2 타일을 붙일 수 있는 경우의 수)
        int[] D = new int[n + 1];
        // D 배열 초기화
        D[1] = 1;
        D[2] = 2;
        for (int i = 3; i <= n; i++) {
            // D[i] = D[i - 1] + D[i - 2]의 결과에 1000000007 나머지 연산을 수행하여 저장
            D[i] = (D[i - 1] + D[i - 2]) % 1000000007;
        }
        // D[n]값 반환하기
        return D[n];
    }

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

        int n = 4;

        int result = solution.solution(n);

        System.out.println(result);
    }
}