타일 채우기 | 백준 2133

풀이 전략 :
1. 그림 그려서 풀기
2. 완전 탐색으로 풀기
3. 메모이제이션
4. 함수로 풀기
https://www.algorithmist.com/index.php/UVa_10918

1.그림 그려서 풀어보기

가장 간단하면서도 생각해내기가 어려울 수 있습니다. 이 방법으로 시도하면 정확히 경우의 수를 계산해내면 맞고 실수하면 틀리는 방법입니다.
개인적으로 선호하지는 않습니다.

살펴보면 4보다 큰 n에 대해서 3 x n 타일은 특수 케이스를 갖습니다.
특수 케이스란 크기가 3 x 2짜리인 타일을 연속해서 이어붙여서 만들 수 없는 경우를 말합니다.
dp라는 배열을 가지고 점화식을 유도해 보면
dp(n) = dp(n - 2) * dp(2) + 2 여기서 2는 각 n마다 자기크기만큼을 가지는 특수케이스 2개를 세어준겁니다.
j = n - 2, n - 4, …, 2까지
dp(n) += 2 * dp(j) 특수케이스를 더해줍니다.

n = int(input())
dp = [-1] * (n + 1)
dp[2] = 3
def three_tiling(n):
    if n % 2 != 0:
        return 0
    if dp[n] != -1:
        return dp[n]
    dp[n] = three_tiling(n - 2) * dp[2] + 2 
    special_cases = 0
    for i in range(2, n - 2, 2):
        special_cases += 2 * three_tiling(i)
    dp[n] += special_cases
    return dp[n]
print(three_tiling(n))

2. 완전 탐색으로 풀어보기

선호하는 방법입니다. 시간 복잡도가 상당하지만 동적 계획법을 적용해야하는 문제에서 완전 탐색으로 먼저 구현한 뒤에 메모이제이션을 적용하는 편이 일반적으로 쉽습니다.
완전탐색의 방법은 한 번에 한 줄씩 해결합니다. 이전 입력에 상관없이 현재 3 x 1 한 줄 짜리 타일을 채우는 방법만 생각합니다. 단 타일의 상태는 각 타일이 채워져있을 수도 없을 수도 있습니다.
이를 나타낸 것이 VCT, ONE, TWO, THR입니다. O를 빈 타일, X를 채워진 타일이라고 생각해봅시다.

VCT :
[O]
[O]
[O]

ONE :
[X]
[O]
[O]

[O]
[O]
[X]

TWO :
[O]
[X]
[X]

[X]
[X]
[O]

THR:
[X]
[X]
[X]

이런식으로 나타낼 수 있겠죠. ONE과 TWO에서 제외된 케이스가 있다는 걸 주의합시다. (케이스를 생각해보면 됩니다.)
현재 CELL 타입을 가지고 이를 채울 수 있는 방법도 생각해 봅시다.

CELL 타입이 0일 때는
AA
BB
CC
와 같이 채우거나
A
A
B B
와 같이 채우는 방법이 있습니다.

CELL 타입이 1일 때는
A
A
X

AA
BB
X
로 순서만 바꾸면 모든 케이스를 커버할 수 있습니다.

CELL 타입이 2일 때는
AA
X
X
한가지 경우밖에 없죠.

마지막으로 CELL 타입이 3일 때는
X
X
X
아무것도 하지않고 넘깁니다.

이를 구현한 것이 아래의 코드와 같습니다.

VCT = 0
ONE = 1
TWO = 2
THR = 3

def fill_line(i, cell_type):
    if i == n:
        if cell_type == THR or cell_type == ONE:
            return 1
        return 0
            

    if cell_type == VCT:
        return fill_line(i + 1, THR) + 2 * fill_line(i + 1, ONE)
        
    elif cell_type == ONE:
        return fill_line(i + 1, VCT) + fill_line(i + 1, TWO)
    elif cell_type == TWO:
        return fill_line(i + 1, ONE)
    else:
        return fill_line(i + 1, VCT)

3. 배열에 저장하기

여기까지 이해했다면 배열에 저장하는 것은 매우 쉽습니다.
곧바로 적용해볼게요.

n = int(input())
VCT = 0
ONE = 1
TWO = 2
THR = 3
dp = [[-1] * 4 for _ in range(31)]
def fill_line(i, cell_type):
    if i == n:
        if cell_type == THR or cell_type == ONE:
            return 1
        return 0
    if dp[i][cell_type] != -1:
        return dp[i][cell_type]

    if cell_type == VCT:
        dp[i][cell_type] = fill_line(i + 1, THR) + 2 * fill_line(i + 1, ONE)
        return dp[i][cell_type]
        
    elif cell_type == ONE:
        dp[i][cell_type] = fill_line(i + 1, VCT) + fill_line(i + 1, TWO)
        return dp[i][cell_type] 
    
    elif cell_type == TWO:
        dp[i][cell_type] = fill_line(i + 1, ONE)
        return dp[i][cell_type]
    else:
        dp[i][cell_type] = fill_line(i + 1, VCT)
        return dp[i][cell_type]
print(fill_line(1, 0))

4. 배열 인자를 줄여보기

dp를 1차원으로 줄이는 방법도 있습니다. 아래 링크와 코드를 참고해주세요

이해가 안가시면 링크 참조해주세요.
이미지 출처 : https://www.algorithmist.com/index.php/UVa_10918

fdp = [-1] * (31)
gdp = [-1] * (31)

def f(k):
    if k == 1:
        return 0
    elif k == 2:
        return 3
    if fdp[k] != -1:
        return fdp[k]
    fdp[k] = f(k - 2) + g(k - 1) + g(k - 1)
    return fdp[k]
def g(k):
    if k == 1:
        return 1
    elif k == 2:
        return 0
    if gdp[k] != -1:
        return gdp[k]
    gdp[k] = f(k - 1) + g(k - 2)
    return gdp[k]