[C++] 백준 BOJ 11726 2xn 타일링 / 11727 2xn 타일링 2

문제링크 : https://boj.kr/11726

시뮬레이션을 해보면 아래 그림과 같이 규칙을 찾을 수 있다.

하나의 타일을 1*2로 고정 시키면 N-1의 모든 케이스를 적용할 수 있고

두개의 타일을 2*1 두개로 고정 시키면 N-2의 모든 케이스를 적용할 수 있다.

하지만, 여기서 신기한 점은 1, 2, 3, 5.... 피노나치 수열과 동일한 문제임을 알 수 있다.

// BOJ 11726 2xn 타일링
#include <iostream>
 
using namespace std;
 
int dp[1001];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
    int num;
    cin >> num;
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= num; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
        if (dp[i] >= 10007)
            dp[i] %= 10007;
    }
    cout << dp[num];
 
    return 0;
}

문제링크 : https://boj.kr/11727

11726 문제의 접근 방법과 동일하지만 조건이 1가지 추가되었다.

2*1을 2개 쌓은 것과 2*2 블럭 1개의 경우를 동일하게 생각하여 조건을 2배 해주면 너무 쉽게 풀린다.

// BOJ 11726 2xn 타일링 2
#include <iostream>
 
using namespace std;
 
int dp[1001];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
    int num;
    cin >> num;
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= num; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] * 2;
        if (dp[i] >= 10007)
            dp[i] %= 10007;
    }
    cout << dp[num];
 
    return 0;
}