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

* 공부 목표

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 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

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

 

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

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

---

풀이

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

(참고) 오버 플로우를 방지하기 위해 10,007을 나누는 거라고 함. 출력 시에만 10,007 적용했다가 틀렸다는 답안 받..

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

 

💡왜 피보나치 수열을 접목시켜 생각해야 했을까??

세로의 길이가 항상 2이므로, 가로를 1과 2를 이용하여 나타내는 경우만 고려하면 됨.
즉, n을 1과 2의 합으로 나타내는 방법의 수를 구하는 문제.

하나 하나 경우를 작성하면 패턴이 보인다.
(ex) 2 = (1 + 1) or (2), 3 = (1 + 2) or (2 + 1) or (1 + 1 + 1)
4 = (1 + 1 + 1 + 1) or (1 + 2 + 1) or (2 + 1 + 1) or (1 + 1 + 2) or (2+ 2)

→ 4는 3의 경우의 수에 1을 더한 값과 2의 경우의 수에 2를 더한 값으로 이루어져있음.
→ 다시말해, 4의 경우의 수는 3의 경우의 수와 2의 경우의 수의 합
→ n번째 수의 경우의 수 = n-1 경우의 수 + n-2의 경우의 수
→ DP 배열은 경우의 수를 저장하는 거니까... D[n] = D[n-1] + D[n-2]

 

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

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+2];
        D[1] = 1;
        D[2] = 2;

        if (n < 3) {
            switch (n) {
                case 1 :
                    System.out.print(D[1]); break;
                case 2 :
                    System.out.print(D[2]); break;
                default:
                    System.out.print("잘못 입력함."); break;
            }
        } else {
            for(int i=3; i<n+1; i++) {
                D[i] = (D[i-1] + D[i-2]) %10007;
            }
            System.out.print(D[n]);
        }
        sc.close();
    }
}

 

 

[참고]

https://kosaf04pyh.tistory.com/222

https://leeeehhjj.tistory.com/13