[백준] 11727번, 2xn 타일링2

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

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

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

 

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

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

---

풀이

1. 테이블 정의
 - 2xn크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지 값
1) 입력받은 n의 크기에 해당하는 직사각형을 채울 경우의 수 → 피보나치 수열
2) 경우의 수를 10,007로 나눈 값을 구하고 출력

2. 점화식 : D[n] = D[n-1] + D[n-2]*2
3. 초기값 정하기 : D[0] = D[1] = 1

✅ 점화식 도출 과정

▶n = 2
2 = 1+1, (2)*2
▶n = 3
3 = 1+1+1, (2+1, 1+2)*2
▶n = 4
4 = 1+1+1+1, (1+1+2, 1+2+1, 2+1+1, 2+2) *2

 

Scanner만 활용하였고, 메모리 17756KB - 시간 212ms 소요.

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] D = new int[n+1];
        D[0] = D[1] = 1;

        if (n < 2) {
            System.out.print(1);
        } else {
            for(int i=2; i<n+1; i++) {
                D[i] = (D[i-1] + D[i-2]*2) %10007;
            }
            System.out.print(D[n]);
        }
        sc.close();
    }
}

 

[참고]

2023.06.21 - [알고리즘] - [백준] DP - 11726번, 2xn 타일링(점화식 도움)