[Programmers][Python] 아방가르드 타일링

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/181186

프로그래머스

 

아방가르드 하면 떠오르는 대표 주자..

처음 작성한 코드

패턴의 수

먼저 가능한 패턴을 세보자. (3x3에서 1x3과 2x3로 나뉘는 경우 처럼 하위 문제로 나뉠 수 있는 개수는 세지 않는다)

1x3에서는 1x3의 막대 하나만 존재할 수 있다.

2x3에서는 ㄱ자 모양의 타일 두 개를 이용해 두 가지 경우를 만들 수 있다.
3x3에서는 그림과 같이 5가지 경우를 만들 수 있다.

1x3, 2x3, 3x3 패턴의 모습

 

4x3, 5x3, 6x3은 다음과 같이 2, 2, 4 경우의 수가 존재한다.

4x3, 5x3, 6x3 패턴의 모습

7x3부터는 각 4x3, 5x3, 6x3 사이에 3x1 막대를 여러 번 넣어 늘리는 식으로 이용가능하다.

아래 패턴은 위의 4x3, 5x3, 6x3 패턴을 3x1막대를 가로로 끼워놓을 수 있게 분리한 모습이다.

이런 식으로 4x3부터는 [2, 2, 4] 경우의 수가 반복되어 나타남을 알 수 있다.

 

DP의 이용

DP의 목적은 복잡한 i번째 경우의 수를 이전 경우의 수에서 패턴의 수를 합한 값으로 계산하는 것이다.

하지만 이 문제에서는 [2, 2, 4] 패턴이 반복됨을 알기 때문에,  n번째 경우의 수를 구하려면 n-1부터 1번째까지의 모든 경우의 수를 참고해야 하므로, O(n²)의 시간복잡도가 발생한다.

 

이를 해결하는 방법은 [2, 2, 4] 패턴이 반복되는 구간을 재활용하는 것이다.

아래의 식에서는 dp[6]은 dp[9]의 2~0번째의 패턴들이 중복되는 것을 볼 수 있다.

dp[6] = dp[5] + 2 * dp[4] + 5 * dp[3] + (2 * dp[2] + 2 * dp[1] + 4 * dp[0])
dp[7] = dp[6] + 2 * dp[5] + 5 * dp[4] + (2 * dp[3] + 2 * dp[2] + 4 * dp[1]) + (2 * dp[0])
dp[8] = dp[7] + 2 * dp[6] + 5 * dp[5] + (2 * dp[4] + 2 * dp[3] + 4 * dp[2]) + (2 * dp[1] + 2 * dp[0])
dp[9] = dp[8] + 2 * dp[7] + 5 * dp[6] + (2 * dp[5] + 2 * dp[4] + 4 * dp[3]) + (2 * dp[2] + 2 * dp[1] + 4 * dp[0])

dp[i]에서 dp[i-4], dp[i-5], dp[i-6]을 제외한 이전 부분은 전에 한번 계산되었다는 점과 같은데, dp[0]을 기준으로 [2, 2, 4], [2, 2, 4], [4, 2, 2] 3가지 순서의 경우를 분리하여 케이스에 저장하여 다음 +3 패턴에 재활용하면 이전 모든 경우의 수를 참고하지 않아도 된다.

 

def solution(n):
    MOD = 1000000007
    dp = [1, 1, 3] + [0] * n
    extended_patterns = [0, 0, 0]
    
    for i in range(3, n + 1):
        extended_patterns[i%3] += (dp[i - 4] * 2 + dp[i - 5] * 2 + dp[i - 6] * 4) % MOD
        dp[i] = (dp[i - 1] + dp[i - 2] * 2 + dp[i - 3] * 5 + extended_patterns[i%3]) % MOD
            
    return dp[n]

 

다른 코드

점화식 사용

위의 반복되는 부분을 수학적으로 정리하여 더 간단하게 표현할 수 있다.

dp[i] = dp[i-1] + 2*dp[i-2] + 5*dp[i-3] + 2*dp[i-4] + 2*dp[i-5] + 4*dp[i-6] + 2*dp[i-7] + 2*dp[i-8] + 4*dp[i-9] + ...

기존 패턴에 따라 i-4부터는 계수가 2, 2, 4가 계속 반복된다.

dp[i-3] = dp[i-4] + 2*dp[i-5] + 5*dp[i-6] + 2*dp[i-7] + 2*dp[i-8] + 4*dp[i-9] + ...

i-3은 다음과 같은 식으로 표시할 수 있는데, i-7부터는 dp[i]와 동일한 것을 볼 수 있다.

dp[i] - dp[i-3] = dp[i-1] + 2*dp[i-2] + 5*dp[i-3] + dp[i-4] - dp[i-6]

dp[i]와 dp[i-3]의 차를 구한다면, i-7부터는 상쇄되어 6개의 이전 항으로부터 값을 유도할 수 있고,

dp[i] = dp[i-1] + 2*dp[i-2] + 6*dp[i-3] + dp[i-4] - dp[i-6]

위와 같이 간단한 식으로 정리된다.

 

따라서 다음과 같이 특정 패턴에 대한 캐시를 만들지 않고 간단한 코드로 작성될 수 있다.

def solution(n):
    MOD = 1000000007
    dp = [1, 1, 3, 10] + [0] * (n)
    
    for i in range(4, n + 1):
        dp[i] = (dp[i-1] + 2 * dp[i-2] + 6 * dp[i-3] + dp[i-4] - dp[i-6]) % MOD
            
    return dp[n]