[Baekjoon/C++] 33675번 - L-트로미노 타일링

[백준] Baekjoon Online Judge

문제로 이동

 

문제

 3×N 크기의 직사각형을 L-트로미노 타일로 빈칸 없이 채우는 방법의 수를 구하는 프로그램을 작성하자.

L-트로미노 타일은 1×1 블록 3개를 L 모양으로 이어서 붙인 도형이고 회전하여 사용할 수 있다.

위 그림은 3×4 크기의 직사각형을 채운 한 가지 방법이다.

 

입력

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.

두 번째 줄부터 각 테스트 케이스마다 하나의 줄에 양의 정수 N이 주어진다.

 

출력

각 테스트 케이스마다 3×N 크기의 직사각형을 채우는 경우의 수를 한 줄에 하나씩 순서대로 출력한다.

 

제한

•  1≤T≤100
•  1≤N≤100

 

---

풀이

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        if (N % 2 == 1) cout << "0\n";
        else {
            long long cnt = 1;
            for (int i = 0; i < N / 2; i++) cnt *= 2;

            cout << cnt << '\n';
        }
    }

    return 0;
}

 L-트로미노 타일은 어떻게 회전하여 사용해도 가로로 2칸을 차지한다. 그렇기에 가로의 길이가 홀수라면 L-트로미노 타일로 직사각형을 모두 채울 수 없다. 그래서 가로의 길이가  홀수라면 0을 출력한다.

 3 * 2크기의 직사각형을 한 세트로 생각했을때, 각 세트에는 2가지 방식으로 타일을 붙일 수 있다. 이를 통해 2^(N / 2)가 문제의 답임을 알 수 있다.