[프로그래머스] 아방가르드 타일링 (python)

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

프로그래머스

정말 대표적인 DP문제 입니다.

점화식으로 풀이하는 방식이 굉장히 신선했습니다.

 

1. 기존 DP 방식

case = ['000', '012', '210', '102', '201', '120', '021']

우선 각 단계의 6가지 케이스를 나누었습니다.

이 케이스는 이전 타일은 완성된 상태에서 튀어나온 칸의 수를 여섯가지 경우로 나눈 것 입니다.

- 0 이 없는 경우는 그 부분에서 다음 dp 단계로 치기 때문에 없습니다.

- 모든 타일의 크기가 3이라 케이스의 총 합이 3의 배수가 되지 않는 경우는 없습니다.

- 긴 타일이 눕히는 경우 (ex. 003) 같은 경우는 따로 계산에서 생각해 주어 넣지 않았습니다.

 

이후 각 상황에 따라 추가할 수 있는 타일링으로 dp를 해주었습니다.

참고로 dp를 할 때 기존 빈칸 (0인 부분)을 채우면서도, 채우는 과정에 이전 dp 과정이 겹쳐 이중 계산이 되지 않아야하는 조건을 잘 생각해 주셔야합니다.

각 상황에 대한 설명은 주석을 달아놓도록 하겠습니다.

def solution(n):
    answer = 0
    case = ['000', '012', '210', '102', '201', '120', '021']
    dp = [dict.fromkeys(case, 0) for _ in range(4)]
    dp[0]['000']= 1
    l = 0
    while l < n:
        dp[0]['000'] %= 1000000007
        dp[0]['012'] %= 1000000007
        dp[0]['210'] %= 1000000007
        dp[0]['102'] %= 1000000007
        dp[0]['201'] %= 1000000007
        dp[0]['120'] %= 1000000007
        dp[0]['021'] %= 1000000007
        
        # 000
        ## 1자 블록 하나를 세워 추가하는 경우
        dp[1]['000'] += dp[0]['000']
        ## ㄱ자 블록 하나와 1자 블록 하나를 눕혀 추가하는 경우
        dp[1]['102'] += dp[0]['000']
        dp[1]['201'] += dp[0]['000']
        dp[1]['012'] += dp[0]['000']
        dp[1]['210'] += dp[0]['000']
        ## ㄱ자 블록 두개를 조합해 추가하는 경우
        dp[2]['000'] += dp[0]['000']
        dp[2]['000'] += dp[0]['000']
        ## 1자 블록 세개를 모두 눕혀 추가하는 경우
        dp[3]['000'] += dp[0]['000']
        ## 주의) 이외의 경우는 자체적 상황에 종속됨
        
        # 012
        ## 1자 블록이 눕혀 추가하는 경우
        dp[1]['201'] += dp[0]['012']
        ## ㄱ자 블록을 채워 넣는 경우
        dp[2]['000'] += dp[0]['012']
        
        # 210
        ## 1자 블록이 눕혀 추가하는 경우
        dp[1]['102'] += dp[0]['210']
        ## ㄱ자 블록을 채워 넣는 경우
        dp[2]['000'] += dp[0]['210']
        
        # 102
        ## 1자 블록이 눕혀 추가하는 경우
        dp[1]['021'] += dp[0]['102']
        ## ㄱ자 블록을 채워 넣는 경우
        dp[2]['000'] += dp[0]['102']
        
        # 201
        ## 1자 블록이 눕혀 추가하는 경우
        dp[1]['120'] += dp[0]['201']
        ## ㄱ자 블록을 채워 넣는 경우
        dp[2]['000'] += dp[0]['201']
        
        # 120
        ## 1자 블록이 눕혀 추가하는 경우
        dp[1]['012'] += dp[0]['120']
        
        # 021
        ## 1자 블록이 눕혀 추가하는 경우
        dp[1]['210'] += dp[0]['021']
        
        dp = dp[1:] + [dict.fromkeys(case, 0)]
        l += 1
    return dp[0]['000'] % 1000000007

 

2. 점화식을 이용하는 방식

다른 사람의 풀이를 보니 특수 경우를 고려하여 점화식을 세우는 풀이가 있었습니다.

특수 경우란 세로로 나뉘는 상황없이 타일링을 완성하는 경우를 말합니다.

다시말해 다른 경우의 조합이 아닌 유일한 방식의 타일링된 경우를 말합니다.

이 경우들에 대해서는 다음 블로그에서 확인하실 수 있습니다.

https://velog.io/@kjy2134/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%95%84%EB%B0%A9%EA%B0%80%EB%A5%B4%EB%93%9C-%ED%83%80%EC%9D%BC%EB%A7%81-%ED%8C%8C%EC%9D%B4%EC%8D%AC

프로그래머스 : 아방가르드 타일링 - 파이썬

따라서 특수 경우는 n에 따라서 1, 2, 5, 2, 2, 4, 2, 2, 4, ... 이런 반복을 띄게 됩니다.

(사실 이 경우가 유일한 특수 경우인지에 대한 증명이 없는 점에서는 이 풀이에 아쉬움이 있습니다.)

이를 통해 특수 케이스에 따라 dp 식을 세울 수 있고 이때 n에 n-3을 대입해 주고 양변을 빼서 점화식을 세울 수 있습니다.

a(n) = a(n-1) + 2 * a(n-2) + 5 * a(n-3) + 2 * a(n-4) + 2 * a(n-5) + 4 * a(n-6) + 2 * a(n-7) + 2 * a(n-8) + 4 * a(n-9) + ...
a(n-3) = a(n-4) + 2 * a(n-5) + 5 * a(n-6) + 2 * a(n-7) + 2 * a(n-8) + 4 * a(n-9) + ...

a(n) - a(n-3) = a(n-1) + 2 * a(n-2) + 5 * a(n-3) + a(n-4) - a(n-6)
a(n) = a(n-1) + 2 * a(n-2) + 6 * a(n-3) + a(n-4) - a(n-6)

 

이로써 다른 풀이들에서 볼 수 있는 아래의 코드 식이 나오게 됩니다.

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