문제 링크
문제 요약
2 x N 크기의 직사각형을 “L-트로미노” 조각들로 타일링하는 가능한 경우의 수를 계산하는 문제입니다.
풀이
이 문제는 2 x N 보드 타일링에 대한 전형적인 Dynamic Programming 문제처럼 보이지만, 사실 간단하게 해결 가능합니다.
- 먼저, 만약 N이 홀수라면, 절대 타일링이 불가능합니다.
- N이 짝수인 경우
2 ** (N // 2)가 답이 됩니다.- L-트리미노 조각을 2칸 내에 배치하는 경우의 수는 2입니다.
- L-트리미노 조각이 2칸 을 넘어 겹쳐서 배치할 수 있는 경우의 수는 존재하지 않습니다. 따라서 무조건 2칸씩 쪼개서 배치하게 됩니다.
정답 코드
def solve():
n = int(input())
if n % 2 == 1:
return 0
return 2 ** (n // 2)
if __name__ == "__main__":
tc = ii()
for t in range(1, tc+1):
ret = solve()
print(ret)