프로그래머스(Programmers) : 산 모양 타일링 - python 풀이

🔴 문제 개요

문제 원문 - 프로그래머스(Programmers)

🚀 난이도 : LEVEL 3

본 문제는 2024 KAKAO WINTER INTERNSHIP 에 출제된 문제로, 알고리즘 스터디 4주차 첫 번째 문제로 다뤘습니다. 또한, 본 풀이는 2024 카카오 겨울 인턴십 코딩테스트 문제해설을 참고했습니다.

한 변의 길이가 1인 정삼각형 2n+1개를 이어붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있습니다. 이때 사다리꼴의 윗변과 변을 공유하는 n개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 새로운 모양을 만들었습니다.

위 예시는 n이 4이고, 1번째, 2번째, 4번째 정삼각형 위에 정삼각형을 붙인 모양입니다.

이렇게 만든 모양을 정삼각형 타일 또는 정삼각형 2개를 이어 붙인 마름모 타일로 빈 곳이 없도록 채우려고 합니다.

정삼각형 타일과 마름모 타일은 돌려서 사용할 수 있습니다. 이때 문제 설명에 따라 만든 모양을 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 10007로 나눈 나머지를 구하는 문제입니다.

제한 사항

• 1 ≤ n ≤ 100,000
• tops의 길이 = n
  • tops[i]는 사다리꼴의 윗변과 변을 공유하는 i+1번째 정삼각형의 위쪽에 정삼각형을 붙이는 경우 1, 붙이지 않는 경우 0입니다.

🟠 Solution

주어진 타일을 가지고, 격자를 모두 채우는 dp의 타일링 유형 문제입니다. 해당 유형은 대게 1 ~ n까지의 칸을 Tabulation하는 방법으로 풀이할 수 있고, 특정 k칸을 채우는 경우의 수를 구하기 위해 k-1칸의 경우의 수를 활용하여 Table을 채워나갈 수 있습니다.

이때 중요한 것은 k-1칸까지의 경우의 수를 k칸에 어떻게 활용할 지를 파악하는 것입니다. 단순히 k-1칸까지 경우의 수에 새로운 경우의 수를 곱해서 k칸을 채울 수도 있고, 어려운 문제의 경우 추가적인 예외를 고려해주어야 합니다.

🚨 Base Condition

Tabulation을 위해서는 Base Condition을 파악하는 것이 중요합니다. 한 칸의 사다리꼴을 채우기 위한 Base Condition을 알아보겠습니다.

한 칸의 top을 포함한 사다리꼴을 채우는 경우의 수는 위와 같이 4개의 경우의 수로 나눠볼 수 있습니다. 이는 가운데 존재하는 하나의 아래 방향 정삼각형을 채우는 경우의 수와 같네요. 각 경우의 수를 1번, 2번, 3번 으로 지칭하고, 정삼각형으로만 채우는 경우를 4번으로 지칭하겠습니다.

즉, 해당 사다리꼴에 top이 존재한다면 4개의 경우의 수, 존재하지 않는다면 3개의 경우가 base condition으로 존재합니다.

🚨 k-1칸 까지와 k칸 까지의 모양에서 겹치는 부분

이때, 예외는 대개 k-1칸 까지의 모양과 k칸 까지의 모양에서 겹치는 부분이 있는 경우 발생합니다. 예시를 보겠습니다.

사다리꼴을 이어붙혔을 때, 점선부분이 겹치게 됩니다. 여기서 알 수 있는 점은 만약 k-1칸의 사다리꼴을 3번으로 채웠다면 k칸의 사다리꼴을 2번으로 채울 수 없게 됩니다. 겹치면 안되니까요.

반면, k-1칸의 사다리꼴을 1, 2, 4번으로 채우는 경우엔 k칸의 사다리꼴을 채우는 경우에 영향을 주지 않습니다.

따라서 k-1칸의 사다리꼴을 3번으로 채웠을 때 영향을 고려하기 위해 Tabulation을 위한 dp 테이블을 두 개로 나눠서 진행합니다.

a[k] : k번째 사다리꼴을 3번 방법으로 채운 경우
b[k] : k번째 사다리꼴을 1, 2, 4번 방법으로 채운 경우

🚨 Tabulation

이제 Tabulation을 위해 점화식을 도출해보겠습니다.

a[k]는 k번째 사다리꼴을 3번으로 채웠음을 가정합니다. 따라서 이전 k-1번째 사다리꼴을 어떤 방법으로 채웠던지 간에 영향을 받지 않습니다.

$a[k] = a[k-1] + b[k-1]$

b[k]는 k번째 사다리꼴을 3번이 아닌 다른 방법(1 or 2 or 4번)으로 채웠음을 가정합니다. 앞서 언급했듯이, 이전 방법이 3번인 경우(a[k-1])에는 사다리꼴을2번 방법으로 채우지 못합니다.

그러면 두 경우로 나눠볼 수 있겠네요.

• top[k]인 경우 a[k-1]에 대해 1, 4번 적용 가능, b[k-1]에 대해 1, 2, 4번 적용 가능
• 아닌 경우 1번 적용 불가로, a[k-1]에 대해 4번 적용 가능, b[k-1]에 대해 2, 4번 적용 가능

$b[k] = \begin{cases} a[k-1] \times 2 + b[k-1] \times 3 & \text{if }top[k] \\ a[k-1] + b[k-1] \times 3 & \text{else } \end{cases}$

💻 전체 코드

위 점화식에 맞춰서 top[k]여부에 따라 Tabulation을 진행해주면 a[n]+b[n]을 답으로 도출해낼 수 있습니다. 이 때, 수가 커짐을 고려해 문제의 조건에 맞춰 10007로 mod연산을 해주지 않으면 TLE가 발생함에 유의해야 합니다.

from typing import List

MOD = 10007


def solution(n: int, tops: List[int]) -> int:

    a = [0 for _ in range(n)]   # a[k] : k번째 아래 방향 정삼각형을 3번 방법으로 덮은 경우의 수
    b = [0 for _ in range(n)]   # b[k] : k번째 아래 방향 정삼각형을 1, 2, 4번 방법으로 덮은 경우의 수

    a[0] = 1
    b[0] = 3 if tops[0] else 2

    for k in range(1, n):
        if tops[k]:
            a[k] = a[k-1] + b[k-1]          # 이전 방법에 대한 경우의 수에 대해 모두 3 적용 가능
            b[k] = a[k-1] * 2 + b[k-1] * 3  # 이전 방법이 3인 경우 1, 4 적용 가능 + 이전 방법이 3이 아닌 경우 1, 2, 4 적용 가능
        else:
            a[k] = a[k-1] + b[k-1]          # 이전 방법에 대한 경우의 수에 대해 모두 3 적용 가능
            b[k] = a[k-1] + b[k-1] * 2      # 이전 방법이 3인 경우 4 적용 가능 + 이전 방법이 3이 아닌 경우 2, 4 적용 가능

        a[k] %= MOD     # 주의. 매 연산마다 MOD해주지 않으면 TLE
        b[k] %= MOD

    return (a[-1]+b[-1]) % MOD

📚 고찰

여러 타일링 문제를 경험해봤지만, 이번 문제가 어렵게 다가왔던 이유는 예외를 제 맘대로 찾아내려고 했었기 때문이라고 생각합니다.

문제에서 주어지는 타일의 모양 등의 조건을 고려하지 않으면 생각해볼 수 있는 예외의 범위가 너무 넓습니다. 그 과정에서 쉽게 잘못된 방향으로 빠져버리게 됨을 느꼈습니다.

실생활의 문제가 아니기에, 문제에 주어진 조건에 충실하여 예외를 파악하려 했다면, 생각할 수 있는 예외의 범위를 조건을 적용했을 때로 좁혀 더 쉽게 찾아낼 수 있을 것입니다.

🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!

✏️ Algorithm Study
본 문제의 다른 풀이 및 피드백, 전체 문제 풀이 순서는 위 알고리즘 스터디 Repository에서도 확인 가능합니다.