[카카오 2024] 산 모양 타일링 python

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/258707

공식 해설 : https://tech.kakao.com/posts/610

 

문제 설명

세모를 쌓아 만든 산모양 타일이 있다.

각 산에는 머리(△)가 있을 수도 있고 없을 수도 있다.

tops[i] = 0 이면 i번째 산은 머리(△)가 없고, tops[i] = 1 이면 i번째 산에 머리(△)가 있는 것이다.

위 그림같은 경우 n = 3, tops = [1, 1, 0, 1] 로 입력값이 주어진다.

 

 

이 타일을 마름모 모양 타일과 정삼각모양 타일 두가지로 덮는 경우의 수를 구하면 된다. 각 타일은 회전할 수 있다.

 

해법

처음엔 재귀로 완전탐색을 해볼까 했는데, 각 방법이 유일하다는걸 증명하려면 지도를 list나 set으로 만들고 다 저장놔야해서 너무나도 비효율적이었다.

DP를 적용하기엔 산끼리 겹쳐있어서 점화식이 나올지 걱정 했는데, 인접한 두 산의 규칙이 의외로 간단했다.

산 하나를 채울 수 있는 경우의 수는 네가지이다.

- 위를 보는 마름모

- 왼쪽을 덮는 마름모

- 오른쪽을 덮는 마름모

- 마름모를 안쓰고 덮는 방법

 

첫번째 산에 각 방법을 적용할 수 있는 경우의 수는 쉽게 구할 수 있다.

 

두번째 산에 타일링하는 경우의 수가 생각보다 쉽게 구해진다.

 

두번째 산에 오른쪽 마름모( \ \ )를 놓을 때, 왼쪽 산과는 전혀 겹치는 구역이 없으므로 왼쪽 산에 아무 타일이나 놓을 수 있다.

다만 왼쪽 마름모( / / )를 놓을 때, 왼쪽 산에서 ( \ \ ) 타일을 놓은 경우의 수는 제외해준다.

그리고 산에 머리(△)가 없으면 위쪽 마름모(♢)를 넣을 수 없으니 0으로 채워준다.

 

세번째 산에 타일링하는 경우의 수도 같은 규칙으로 손쉽게 구할 수 있다.

위 세칸짜리 산을 채울 수 있는 경우의 수는 11 + 7 + 11 + 11 = 40 이다.

 

이제 이 로직을 그대로 코드로 구현해주기만 하면 손쉽게 테스트를 통과할 수 있다.

문제 요구조건대로 mod 10007을 해주는 것만 추가되었다.

def solution(n, tops):
    # 0 : /\ \ 마름모, 1 : / /\ 마름모, 2 : ♢, 3 : 마름모X
    table = [[0] * 4 for _ in range(n)]
    tsum = [0] * n
    MAX = 10007
    
    # i = 0인 경우 처리
    table[0][0] = 1
    table[0][1] = 1
    table[0][2] = tops[0]
    table[0][3] = 1
    
    tsum[0] = sum(table[0])
    
    # i > 0에 대해 bottom - up으로 경우의 수 세기
    for i in range(1, n):
        table[i][0] = tsum[i-1]
        table[i][1] = tsum[i-1] - table[i-1][0]
        table[i][2] = tsum[i-1] if tops[i] else 0
        table[i][3] = tsum[i-1]
        
        tsum[i] = sum(table[i]) % MAX
    
    return tsum[n-1]