[BOJ] (G2) 11333. 4 x n 타일링

👨‍💻 개인 공부 기록용 블로그 입니다.
💡 틀린 내용이나 오타는 댓글, 메일로 제보해주시면 감사하겠습니다!! (__)

링크

https://www.acmicpc.net/problem/11333

문제

문제 설명 및 요점

• 단위 타일의 크기는 3x1이다.
• 가로의 길이 \( n \)은 10000 이하의 자연수이다. 또한 단위 타일 길이가 3 이므로, \( n \)은 3의 배수여야만 한다.
  • \( n \)이 3의 배수가 아니라면, 넓이가 홀수인 단위 타일로는 넓이가 짝수인 타일을 채울 수 없다.
• 경우의 수를 1000000007로 나누어 리턴해야 한다.

풀이

#DP

• 타일링 문제는 DP로 분류된다.
  • 이전 타일 배치 경우의 수가 지속적으로 활용되기 때문이다.
• 점화식을 찾아보자. \( n = 3 \)인 경우와 \( n=6 \)인 경우는 문제에 주어져있다. \( n=3 \)인 경우를 시각화하면 다음과 같다.

\( n=6 \) 인 경우, 3 x n 타일링과 비슷하게 \( n=3 \) 인 경우 2개로 쪼갤 수 있다. dp[n] = 가로가 n일때, 4xn 타일링의 경우의 수로 정의하면, dp[6] = dp[3] * dp[3] + ?이다. +?에 해당하는 \( n=6 \)인 경우의 유니크한 단위 타일을 찾아보자. 3 x n 타일링 문제와 마찬가지로, 양 끝에 세로 타일을 세우는 것으로 유니크한 단위 타일을 만들 수 있다. 윗면 기준으로 1131과 1311로 쪼갤 수 있으며, 밑면과 윗면을 대칭시킬 수 있으므로 4가지의 경우의 수가 추가로 나온다. 이를 시각화하면 아래와 같다.

그림을 보면 1131 과 1311로 표기한 것을 이해하기 쉽다. 맨 윗줄만 봤을 때 나눠지는 타일의 넓이라고 생각하면 된다. 맨 아래에 가로 타일로만 채워지는 밑줄이 맨 윗줄로 올라가는 경우도 있기 때문에 총 4가지 인 것이다.

\( n=9 \)인 경우도 도출해보자. 3 x n 타일링의 빌드업을 이해했다면, 이 식까지는 문제없이 도출할 수 있다. dp[9] = dp[6] * dp[3] + dp[3] * (dp[6]의 유니크 단위 타일 수) + ?
\( n=9 \)의 유니크한 단위 타일을 찾아보자. \( n=6 \)일 때와 마찬가지로, 양 끝에 세로 타일을 위치시키고 내부를 채우면 된다. 다만, 내부에는 꼭 가로 타일이 2개 쓰여야 한다. 1개 쓰이는 경우는 \( n=6 \)일 때의 유니크 단위 타일과 겹치게 된다. 11331, 13131, 13311 총 3가지를 구할 수 있으며, 밑면과 윗면을 대칭시킬 수 있으므로 총 6가지 경우의 수가 나오게 된다.

유니크한 단위 타일의 경우의 수에도 규칙이 있다. 유니크한 단위 타일은 항상 양 끝에 세로 타일을 위치시키는 경우로 부터 출발하고, 해당 케이스에서 써야만 하는 가로 타일의 수가 결정되어 있기 때문에, 아래 그림과 같이 일반화할 수 있다.

\( n / 3 - 1 \) 개의 가로 타일은 항상 가로 길이가 \( n-3 \)이다. 양 끝에 세로 타일 1개씩 존재하므로 남은 가로 길이는 1이다. 즉, 위 사진에서 초록색으로 채워진 부분의 세로 타일 개수는 항상 1개이다. 이를 이용하면, 초록 부분을 채우는 유니크한 단위 타일의 경우의 수를 수식화할 수 있다. 1개의 세로 타일 위치만 결정해주면 되므로, 총 \( n/3 -1 \)개의 경우의 수가 존재하며, \( n \)이 3의 배수이기 때문에 이는 \( n * 2 / 3 \)으로 바꾸어 계산할 수 있다.

따라서, 점화식을 도출하면 다음과 같다.

dp[n] = dp[n-3] * 3 + dp[n-6] * (n=6의 유니크 타일 경우의 수) + ...

dp[n] = dp[n-3] * 3 + dp[n-6] * 6 * 2 / 3 + dp[n-9] * 9 * 2 / 3

2중 for문을 통해 계산하면, \( O(N^2) \)로 통과할 수 있다. 참고로 3 x n 타일링 처럼 수식을 정리하며 \( O(N) \) 풀이도 가능하다.

코드

import sys
input = sys.stdin.readline
INF = 1_000_000_007

dp = [0] * 10001
dp[0] = 1
dp[3] = 3
for i in range(6, 10001, 3):
    dp[i] = dp[i - 3] * 3
    for j in range(6, i + 1, 3):
        dp[i] += dp[i - j] * j * 2 // 3
    dp[i] %= INF

T = int(input())
for _ in range(T):
    print(dp[int(input())])