[백준 11727번 C++] 2xn 타일링 2

11727번: 2×n 타일링 2 (acmicpc.net)

11727번: 2×n 타일링 2

---

규칙을 알아보자!
 
n=1 일 때, 1가지
n=2 일 때, 3가지
n=3 일 때, 5가지 (모두 세로 1가지 + 1개만 세로 2가지, 2*2 한개가 포함된 거 2가지)
n=4 일 때, 11가지(모두 세로 1가지, 모두 가로 1가지+ 2개만 가로 3가지+ 2*2 한개가 포함된 거 5가지+ 2*2 두개가 포함된 거 1가지)
n=5 일 때, 21가지
1. 모두 세로:  1가지
2. 세로 1개, 가로 4개: 3개

3. 세로 3개, 가로 2개: 4개

4. 2*2 1개: 3+3+2+2 = 10개

5. 2*2 2개: 3개

n=8일 때, 171가지 (예제 출력 2번)

점화식을 구해보면

T(n) = 2*T(n-2) + T(n-1)

 

이게 맞는 지 확인하려면 n=8까지 구해서 출력 경우가 맞는 지 확인해보면 됨

위 점화식이 맞다면

n=6 일 때, 11*2 + 21 = 43가지

n=7 일 때, 2*21 + 43 = 85가지

n=8 일 때, 2*43 + 85 = 171 가지 => 맞음

 

-> 사실 안그려보고 구하다가 계속 틀렸었다

직접 펜으로 그리니까 정확히 구해지고 점화식 규칙을 예상할 수 있었다

절대 귀찮아하지 말고 직접 풀어보자,,

 

점화식이 너무 어려웠는데, 점화식만 구해지니까 코드는 쉬웠다

최종 코드는

#include <iostream>
using namespace std;

int N;
int arr[1001];

int main() {
    cin >> N;

    arr[1] = 1;
    arr[2] = 3;
    arr[3] = 5;
    for (int i=4;i<=N;i++)
        arr[i] = (2*arr[i-2] + arr[i-1]) %10007;
    cout << arr[N];

}