[프로그래머스] 산 모양 타일링

문제 요약

윗변의 길이가 n, 아랫변의 길이가 n + 1인 삼각형 사다리꼴이 있다.

각 위치의 위쪽에는 tops[i]의 값에 따라 삼각형이 하나 더 붙을 수 있다.

• tops[i] == 1: 위쪽 삼각형이 붙어 있다.
• tops[i] == 0: 위쪽 삼각형이 붙어 있지 않다.

이 모양을 정삼각형 타일 또는 정삼각형 2개를 붙인 마름모 타일로 채우는 경우의 수를 구해야 한다.

경우의 수가 클 수 있으므로 결과를 10007로 나눈 나머지를 반환한다.

핵심 아이디어

n의 최대값이 100,000이므로 모든 타일 배치를 직접 탐색할 수 없다.

모양을 왼쪽부터 한 칸씩 채우는 동적 계획법을 사용한다.

현재 칸을 채우는 방법은 바로 이전 칸의 오른쪽 경계가 어떤 상태인지에 따라 달라진다. 따라서 각 칸마다 다음 두 상태만 관리하면 된다.

dp[i][0] = i번째 칸까지 채웠고, 오른쪽으로 튀어나온 마름모가 없는 경우
dp[i][1] = i번째 칸까지 채웠고, 오른쪽 경계에 마름모를 놓은 경우

마지막 칸까지 처리한 뒤에는 두 상태 모두 완성된 타일 배치이므로 둘을 더한다.

점화식

위쪽 삼각형이 없는 경우

tops[i] == 0이면 현재 칸을 채우는 방법의 수에 따라 다음과 같이 전이한다.

next_zero = 2 * zero + one
next_one = zero + one

따라서 점화식은 다음과 같다.

dp[i + 1][0] = 2 * dp[i][0] + dp[i][1]
dp[i + 1][1] = dp[i][0] + dp[i][1]

위쪽 삼각형이 있는 경우

tops[i] == 1이면 위쪽 삼각형을 단독 삼각형으로 채우거나, 아래 삼각형과 묶어 마름모로 채우는 선택이 추가된다.

next_zero = 3 * zero + 2 * one
next_one = zero + one

따라서 점화식은 다음과 같다.

dp[i + 1][0] = 3 * dp[i][0] + 2 * dp[i][1]
dp[i + 1][1] = dp[i][0] + dp[i][1]

오른쪽 경계에 마름모를 놓는 방법은 위쪽 삼각형의 유무와 관계없이 한 가지이므로 dp[i + 1][1]의 점화식은 동일하다.

풀이 과정

1. DP 초기값 설정

아직 아무 칸도 처리하지 않은 상태에서는 오른쪽으로 연결된 마름모가 없는 경우만 한 가지 존재한다.

zero = 1
one = 0

2. 왼쪽부터 각 칸 처리

tops를 순회하면서 위쪽 삼각형의 존재 여부에 맞는 점화식을 적용한다.

for top in tops:
    if top == 1:
        next_zero = 3 * zero + 2 * one
    else:
        next_zero = 2 * zero + one

    next_one = zero + one

3. 나머지 연산

경우의 수가 빠르게 커지므로 매 단계에서 10007로 나눈다.

zero = next_zero % 10007
one = next_one % 10007

4. 두 상태 합산

모든 칸을 처리한 뒤 두 상태의 경우의 수를 더한다.

return (zero + one) % 10007

Python 코드

def solution(n, tops):
    MOD = 10007

    # 아직 아무 칸도 처리하지 않은 초기 상태
    zero = 1
    one = 0

    for top in tops:
        if top == 1:
            next_zero = 3 * zero + 2 * one
        else:
            next_zero = 2 * zero + one

        next_one = zero + one

        zero = next_zero % MOD
        one = next_one % MOD

    return (zero + one) % MOD

코드 설명

zero

zero = 1

현재까지 타일을 채웠을 때 오른쪽 경계에 마름모를 놓지 않은 경우의 수다.

아무 칸도 처리하지 않은 초기 상태는 한 가지이므로 1로 시작한다.

one

one = 0

현재까지 타일을 채웠을 때 오른쪽 경계에 마름모를 놓은 경우의 수다.

초기에는 놓은 타일이 없으므로 0으로 시작한다.

tops[i]에 따른 전이

if top == 1:
    next_zero = 3 * zero + 2 * one
else:
    next_zero = 2 * zero + one

위쪽 삼각형이 붙어 있으면 현재 칸에서 만들 수 있는 타일 배치가 한 가지씩 더 많아진다.

이 차이 때문에 top == 1일 때는 계수가 3, 2가 되고, top == 0일 때는 2, 1이 된다.

오른쪽 경계 상태

next_one = zero + one

오른쪽 경계에 마름모를 놓는 방법은 이전 상태마다 한 가지씩 존재한다.

따라서 이전의 두 상태를 더하면 된다.

두 변수만 사용하는 이유

현재 상태는 바로 이전 상태만 필요하다.

크기가 n인 DP 배열 전체를 저장할 필요가 없으므로 zero, one 두 변수만 사용해 공간을 줄일 수 있다.

간단한 예시

n = 1, tops = [0]인 경우를 살펴보자.

초기 상태는 다음과 같다.

zero = 1, one = 0

위쪽 삼각형이 없으므로 다음 점화식을 적용한다.

next_zero = 2 * 1 + 0 = 2
next_one = 1 + 0 = 1

따라서 전체 경우의 수는 다음과 같다.

2 + 1 = 3

시간 복잡도

tops 배열을 한 번만 순회한다.

O(n)

n이 최대 100,000이어도 충분히 처리할 수 있다.

공간 복잡도

DP 배열을 만들지 않고 고정된 개수의 변수만 사용한다.

O(1)

정리

이 문제는 전체 모양을 왼쪽부터 한 칸씩 나누고, 오른쪽 경계의 상태만 기억하는 동적 계획법 문제다.

풀이 흐름은 다음과 같다.

오른쪽 경계 상태를 두 가지로 구분
tops[i]에 따라 서로 다른 점화식 적용
각 단계에서 10007로 나머지 연산
마지막 두 상태를 더해 정답 계산

모든 배치를 직접 그리거나 탐색하지 않고, 다음 칸에 영향을 주는 정보만 상태로 압축하는 것이 핵심이다.