[프로그래머스] (Lv.2) 3 x n 타일링

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

링크

https://school.programmers.co.kr/learn/courses/30/lessons/12902

문제

문제 설명 및 요점

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

풀이

#DP

• 타일링 문제는 DP로 분류된다.
  • 이전 타일 배치 경우의 수가 지속적으로 활용되기 때문이다.
• 점화식을 찾아보자. \( n = 2 \) 인 경우는 간단하게 구할 수 있으며, \( n=4 \) 인 경우의 수는 문제에 주어져 있다.

\( n=2 \) 로 부터, \( n=4 \) 를 어떻게 도출할 수 있을까? dp[n] = 가로가 n일때, 3xn 타일링의 경우의 수 라고 정의해보자. dp[4] = dp[2] * dp[2] + ?로 볼 수 있다. 가로 길이 4를 2와 2로 쪼갤 수 있고, 가로 길이 2는 dp[2] 를 통해 이미 구했기 때문이다. 하지만 + ? 로 적어놨듯, 아직 구해지지 않은 무언가가 있다.

입출력 예시에도 나와있는데, 아래와 같이 \( n=4 \) 에서만 볼 수 있는 특이한 경우가 있기 때문이다.

따라서 + ?자리에는 2 가 들어간다.

\( n=6 \)인 경우도 이전 케이스들을 이용하여 도출해보자. dp[4]를 통해 가로 길이가 4일 때를 계산하였고, 거기에 가로 길이 2가 늘어난 경우로 볼 수 있다. 이 경우는 dp[4] * dp[2]로 계산할 수 있다. 또한, dp[4]를 계산할 때 \( n=4 \) 에서만 볼 수 있는 유니크한 단위 타일도 찾았기 때문에 이 경우를 더해줘야 한다. 이는 dp[2] * 2(유니크한 단위 타일) 로 계산할 수 있다. 유니크한 단위 타일의 가로 길이가 4였기 때문에 dp[2]를 곱해주었다.

이전 경우와 마찬가지로, \( n=6 \) 에서만 볼 수 있는 특이한 경우가 존재한다.

유니크한 단위 타일을 잘 보면, 이것이 만들어지는 규칙을 도출해낼 수 있다. 윗변 또는 밑변이 가로 타일로만 이루어져 있으며, 양 끝은 세로 타일이 들어간다는 점이다. 이로 미루어 보아, \( n \)이 늘어날 때마다 유니크한 단위 타일이 2개씩 늘어남을 알 수 있다. 꼭 2개씩만 늘어나는 것인가 의문이 들 수 있는데, 색칠한 부분의 타일이 하나라도 세로로 놓이게 되면 이전 경우와 무조건 겹치게 된다. 세로로 놓인 부분이 \( n=2 \)인 경우의 단위 타일과 겹치기 때문이다.

위 케이스들을 통해, 점화식을 도출해보자. \( n > 2 \)인 경우에 대해 아래 수식이 성립한다.

\[ \displaystyle dp[n] = dp[n - 2] * dp[2]+ \sum^{n - 2}_{i = 4}(2 * dp[n - i]) + 2 \]

\( i \)는 짝수이며, 맨 마지막 \( +2 \)는 새로 추가되는 유니크한 단위 타일에 대한 경우의 수이다. dp[0] = 1 로 초깃값을 두어 유니크한 단위 타일에 대한 경우의 수 계산을 간단히 할 수 있다. dp[2] = 3이므로, 아래와 같이 코드를 작성하면 통과할 수 있다.

def solution(n):
    INF = 1_000_000_007
    dp = [0] * 5001
    dp[0] = 1
    dp[2] = 3
    for i in range(4, n + 1, 2):
        dp[i] = (dp[i - 2] * 3)
        for j in range(i - 4, -1, -2):
            dp[i] += (dp[j] * 2)
    return dp[n] % INF

프로그래머스 시간 제한이 넉넉해서 위 코드로도 충분히 통과할 수 있지만, 위 코드는 \( O(N^2) \)로 실제로 돌려보면 굉장히 느리다. 점화식을 정리하여 \( O(N) \) 으로 최적화 할 수 있다.

점화식의 \( +2 \) 부분을 시그마로 합치면, 아래 수식이 된다.

\[ \displaystyle dp[n] = dp[n - 2] * 3+ \sum^{n}_{i = 4}(2 * dp[n - i]) \]

위 수식으로 부터, 양변에서 \( dp[n-2] \)를 빼주면,

\[ \displaystyle dp[n] - dp[n-2] = dp[n - 2] * 2 + \sum^{n}_{i = 4}(2 * dp[n - i]) \]

\[ \displaystyle dp[n] - dp[n-2] = \sum^{n}_{i = 4}(2 * dp[n - i]) \]

이므로, 위 수식으로 점화식의 우항을 정리할 수 있으며, 최종 점화식은 다음과 같다.

\[ \displaystyle dp[n] = 4 * dp[n-2] - dp[n - 4] \]

코드

def solution(n):
    INF = 1_000_000_007
    dp = [0] * 5001
    dp[0] = 1
    dp[2] = 3
    for i in range(4, n + 1, 2):
        dp[i] = (dp[i - 2] * 4 - dp[i - 4]) % INF 
    return dp[n]