백준 알고리즘, 11727 문제

---

개요

이 문제는 11726 문제 (2xn 타일링) 의 다른 버전이다.

11726 문제를 정확히 이해했다면

같은 방식으로 풀어낼 수 있다.

---

풀이

2 x n 타일링 문제에서는 2 x n 타일을 채우기 위해

1 x 2, 2 x 1 타일을 사용했다.

그러나 이 문제에서는 2 x 2 타일이 추가되었다.

무엇이 달라질까?

(1) 2 x 1

(2) 2 x 2

2 x 1 과 2 x 2 를 위와같이 준비해놓았을 때

2 x 3 은 다음과 같이 그릴 수 있다.

(3) 2 x 3

2 x  2 번 그림을 그대로 가져온 후, 오른쪽에 2 x 1 크기의 타일을 세로로 하나 넣는다. ---> 개수 변화 없음.

2 x 1 번 그림을 그대로 가져온 후, 오른쪽에 2 x 1 번 크기의 타일을 가로로 2개 넣는다. ---> 개수가 x 2 가 됨.

2 x 1 번 그림을 그대로 가져온 후, 오른쪽에 2 x 2 번 크기의 타일을 1개 넣는다.

규칙이 나왔으니 점화식을 만들어보자.

DP[n] = DP[n - 1] + DP[n - 2] * 2

---

코드

@github 에서 확인하기

/**
 * @site: https://www.acmicpc.net/problem/11727
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 07. 19
 */
#include <iostream>
using namespace std;

// Iterative DP
int main() {
    int DP[1001];
    int i, n;
    cin >> n;
    DP[0] = 0;
    DP[1] = 1;
    DP[2] = 3;
    for (i = 3; i <= n; i++) {
        DP[i] = (DP[i-1] % 10007) + ((DP[i-2] * 2) % 10007);
    }
    cout << DP[n] % 10007 << endl;
    return 0;
}