[백준 33675번] L-트로미노 타일링 (python)

1. 문제

설명

L-트로미노는 1×1 블록 3개가 L자 형태로 연결된 도형입니다. 이를 회전하거나 대칭해서 사용할 수 있으며, 3×N 보드에 빈틈 없이 채우는 경우의 수를 구하는 것이 목표입니다.

---

2. 오답코드

test = int(input())

for i in range(test) :
    dp = [0,2]
    n = int(input())
    for i in range(n) :
        if i < 2 :
            continue
        if i % 2 == 0 :
            dp[i] = (dp[i-1] + dp[i-2]*2)
        else :
            dp[i] = (dp[i-1] + dp[i-2])
            
    print(dp[n-1])

❌ 오답 코드에서의 실수

• 점화식이 잘못되었음 (일반적인 dp 형태 아님)
• L-트로미노 타일링은 f(n) = 2^(n/2)의 수학적 규칙으로 푸는 문제
• 리스트 인덱싱 오류 발생 가능 (dp[i]를 선언 없이 대입함)

---

3. 정답코드 및 접근법

T = int(input()) 
for _ in range(T):
    N = int(input())
    if N % 2 == 1:
        print(0)
    else:
        print(1 << (N // 2))  # 2의 (N/2) 제곱

1) N이 홀수인 경우

→ 절대 채울 수 없음.
L-트로미노는 3칸을 채우기 때문에 3×N이 홀수일 경우 불가능함.
답 = 0

2) N이 짝수인 경우

→ N = 2k로 놓고 생각.
3×2 타일마다 채울 수 있는 경우는 2가지.
→ 전체는 2^k = 1 << k
답 = 2^(N/2)

---

4. 정리 및 요약

 

• n이 홀수면 무조건 0, 조건문 꼭 넣어야 함.
• L-트로미노는 3칸이지만, 모양상 2열 단위로 맞춰져야만 타일링 가능.