백준 2133 - 타일 채우기

 

www.acmicpc.net/problem/2133

2133번: 타일 채우기

이 문제는 다이나믹 프로그래밍의 대표적인 유형 중 하나인 타일 채우기 관련 문제이다. 타일을 채우는 방식에서 어떠한 규칙성을 찾아 적용시키면 된다. 이 문제도 필자가 이전 포스팅들에서 여러 번 말했듯이 각 정점에서 일정한 규칙을 계속 적용시킬 수 있기에, 정점과 정점 간 각기 다른 간선을 가지는 그래프가 아니라 DP문제임을 생각해 볼 수 있다. 

 

이 문제는 가로변의 길이가 홀수이면 채울수 있는 경우가 없다. 그 점은 조금만 생각해보면 알 수 있다. 가로길이가 짝수인 경우만 생각한다.

일단 3X2의 공간을 채우는 방법부터 살펴보자

그림에서 가장 위에 있는 형태로 3가지를 갖게 된다. 만약에 3X4라면, 3X2의 공간이 2개가 합쳐진 것이므로, 3 x 3 = 9가 되어야 할 것 같지만, 길이가 길어지면 3X2의 공간에서는 불가능했던 다른 형태가 가능해진다. 3X4 공간을 채운 그림을 보자. 가로형 직사각형을 위에나 아래에 몰아주고 아래를 저런 식으로 채우는 2가지의 경우가 존재한다. 이러한 형태는 3X4이상의 공간에서 계속 나타나게 된다. 

3X4, 3X6, 3X8,...이상의 공간에서, 가로형 직사각형이 위나 아래를 채우고, 나머지 부분의 양 끝을 세로형 직사각형이 막아주며, 남은 공간이 모두 가로형 직사각형으로 메워진 형태가 계속 2개씩 나타난다. 

 DP[i]를 3Xi를 채우는 모든 경우의 수라고 정의하자.

위의 그림과 같이, 3X6을 채우는 경우, 바로 이전의 3X4공간에 3X2공간을 덧대주는 방식으로 채울 수 있고, 3X2를 채우는 방법이 3이므로 DP[i-2] X 3으로 경우의 수를 찾을 수 있다. 이제 윗 그림의 아래쪽 부분과 같은 경우를 생각해야 한다. DP[i-4] 다음에 나머지 공간을 채우는 새로운 방법은 2개뿐이므로 DP[i-4]에 2를 곱하여 추가적인 경우를 찾을 수 있다. 하지만 이게 전부가 아니다.

아래와 같이 DP[i-6]에서 나머지 공간을 채우는 2가지의 경우를 곱하는 경우도 고려해야 한다!

즉 위와 같은 형태로 식이 완성된다. DP[0]까지 내려가면서 이전의 모든 히스토리를 참조해야 한다. 그동안의 간단한 DP문제는 바로 직전의 경우만 참조하거나, 직전 2~3개 정도만 보는 경우가 많았으나, 이번 문제에서는 이전 히스토리를 모두 참조해야 한다

 

정리하면 위와같은 점화식이 완성된다. 그리고 이제 i루프만 돌리면 해결할 수 있다.

 

<주요 내용>

다이나믹 프로그래밍, 타일링, DP

 

<코드>

import sys
si = sys.stdin.readline


def main():
    n = int(si())
    if n % 2:
        print(0)
        return

    dp = [0 for _ in range(31)]
    dp[0], dp[2] = 1, 3
    if dp[n]:
        print(dp[n])
        return

    # dp[n]=dp[n-2]*3 + 2 * sum(dp[n-4],dp[n-6],...,d[0])

    for i in range(4, n+2, 2):
        dp[i] = dp[i-2]*3+sum(dp[:i-4+1])*2
    print(dp[n])


if __name__ == '__main__':
    main()