[코테] 백준 2133 python

문제 설명

문제
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

접근 방법

1. 3 X N의 경우 나눠보기

   1. 3 x 0

      = 1 (근데 여기서 0이라고 할뻔 했다)

   2. 3 x 1

      = x

   3. 3 x 2

      = 3

   4. 3 x 3

      = x

   5. 3 x 4

      = 3 x 3 + 2 (중간에 연결이 되는 경우

   6. 3 x 5

      = x

   7. 3 x 6 ( 이 부분을 떠올리기 힘들었음)

      = 3×(N-2) 크기의 벽을 채운 후, 3×2 크기의 새로운 공간을 추가하는 방법 + 3×(N-4) 크기의 벽을 채운 후, 특수한 모양의 블록(새로운 모양)으로 채우는 방법 + 3×(N-6) 크기의 벽을 채운 후, 특수한 모양의 블록(새로운 모양)으로 채우는 방법

코드

N = int(input())

# dp 테이블 초기화
d = [0] * (N + 1)
d[0] = 1  # 3×0 크기의 벽을 채우는 경우는 1가지 (아무것도 놓지 않는 경우)

if N >= 2:
    d[2] = 3  # 3×2 크기의 벽을 채우는 경우는 3가지

# 짝수 크기만 계산
for i in range(4, N + 1, 2):
    d[i] = d[i - 2] * 3  # 기본적인 경우

    # 특수한 경우를 하나씩 직접 추가
    if i >= 4:
        d[i] += d[i - 4] * 2
    if i >= 6:
        d[i] += d[i - 6] * 2
    if i >= 8:
        d[i] += d[i - 8] * 2
    if i >= 10:
        d[i] += d[i - 10] * 2
    if i >= 12:
        d[i] += d[i - 12] * 2

print(d[N])

(선택사항) 오류 해결

💡 순서는 왜 고려하지 않아도 될까?

우리가 d[N]을 구할 때, d[N-2], d[N-4], d[N-6] 등을 활용하는 방식이 중복을 자동으로 포함

(1) 타일을 채우는 방식이 "순차적"으로 진행

우리는 항상 왼쪽부터 오른쪽으로 타일을 채운다고 가정

예를 들어, d[N]을 구할 때는 항상 3×(N-2)까지 채워진 상태에서 새로운 3×2 블록을 추가하는 방식을 고려.

✔ d[N-2]를 먼저 계산 → 이미 3×(N-2)까지는 채워진 상태

✔ 그 상태에서 3×2 블록을 추가하면 d[N-2] * 3

✔ 3×(N-4)까지 채워진 후 특수한 타일을 추가하는 경우도 자동으로 포함

즉, 순서를 고민할 필요 없이 이전 결과를 그대로 가져오면서 새로운 블록을 추가하는 방식이라 중복 계산이 없고, 순서도 자연스럽게 포함

---

(2) 특수한 경우는 항상 2가지 방향이 존재

우리가 특수한 경우를 d[N-4] * 2처럼 곱하기 2를 하는 이유도 순서와 관련

예를 들어, 3×4 크기의 특수 블록이 있다면

이 블록을 전체 3×N 크기의 벽에서 사용할 때,

1️⃣ 왼쪽에 놓을 수도 있고,

2️⃣ 오른쪽에 놓을 수도 있음

✔ 그래서 * 2를…

✔ 이렇게 하면 자연스럽게 모든 배치 순서가 자동으로… 포함