[PG/Python] 산 모양 타일링

문제

https://school.programmers.co.kr/learn/courses/30/lessons/258705

프로그래머스

풀이 참조

https://tech.kakao.com/2023/12/27/2024-coding-test-winter-internship/

2024 카카오 겨울 인턴십 코딩테스트 문제해설

---

알고리즘 분류

•  다이나믹 프로그래밍

문제

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

이렇게 만든 모양을 정삼각형 타일 또는 정삼각형 2개를 이어 붙인 마름모 타일로 빈 곳이 없도록 채우려고 합니다. 정삼각형 타일과 마름모 타일은 돌려서 사용할 수 있습니다.

타일을 놓을 때 다른 타일과 겹치거나 모양을 벗어나게 놓을 수는 없습니다. 위의 예시 모양을 채우는 방법 중 일부는 다음과 같습니다.

사다리꼴의 윗변의 길이를 나타내는 정수 n과 사다리꼴 윗변에 붙인 정삼각형을 나타내는 1차원 정수 배열 tops가 매개변수로 주어집니다. 이때 문제 설명에 따라 만든 모양을 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 10007로 나눈 나머지를 return 하도록 solution 함수를 완성해 주세요.

제한사항

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

입출력 예제

n	tops	result
4	[1, 1, 0, 1]	149
2	[0,1]	11
10	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]	7704

예 #1 문제의 예시와 같습니다. 문제에서 설명한 방법을 포함해 총 149가지 방법이 존재합니다. 따라서 149를 return 해야 합니다.

예 #2 문제 설명에 따라 만든 모양은 다음과 같습니다. 이 모양을 타일로 채우는 방법은 다음과 같이 총 11가지입니다. 따라서 11을 return 해야 합니다.

예 #3 경우의 수는 총 17,711가지입니다. 따라서 17711을 10007로 나눈 나머지인 7704를 return 해야 합니다.

---

풀이

사실 풀이는 이미 위의 링크를 보면 제시 되어있다.

삼각형을 채우는 케이스 1,2,3,4는 다음과 같다.

1. 단, top이 없으면 불가능	2. 앞에서 3의 케이스를 하면 불가능
3. 실행하면 a[k], 아니면 b[k]라 치자.	4.

이번 노드	설명	앞노드 a[k-1]	앞노드 b[k-1]
a[k]	k번째 아래 방향 정삼각형까지 덮되, k번째 아래 방향 정삼각형을 덮는 방법이 3번 방법인 경우의 수
b[k]	k번째 아래 방향 정삼각형까지 덮되, k번째 아래 방향 정삼각형을 덮는 방법이 3번 방법이 아닌 경우의 수	# 1 # 2 불가능 # 4	# 1 # 2 # 4

	a[k]	b[k]
전 노드에 top이 있다 →  tops[k-1]==1	a[k] = a[k-1] + b[k-1]	b[k] = 2 × a[k-1] + 3 × b[k-1]

	a[k]	b[k]
전 노드에 top이 없다 →  tops[k-1]==0	a[k] = a[k-1] + b[k-1]	b[k] = a[k-1] + 2 × b[k-1] #1에 해당되는게 하나씩 빠짐

소스코드

def solution(n, tops):
    MOD = 10007
    a = [0] * (n + 1)
    b = [0] * (n + 1)
    a[0] = 0
    b[0] = 1

    for k in range(1, n + 1):
        if tops[k - 1]:
            a[k] = (a[k - 1] + b[k - 1]) % MOD
            b[k] = (2 * a[k - 1] + 3 * b[k - 1]) % MOD
        else:
            a[k] = (a[k - 1] + b[k - 1]) % MOD
            b[k] = (a[k - 1] + 2 * b[k - 1]) % MOD

    return (a[n] + b[n]) % MOD

---

 2024 카카오 겨울 인턴십 코딩테스트 5번 문제다. 사실 1~4번까지 다 풀고 나서 저 문제를 처음 본 날에는 솔직히 눈에 규칙성조차 잘 안 보였다. 케이스 분해를 정말 잘못했다는걸 다시 풀면서 크게 느낀 것 같다.

 케이스 분해가 복잡하다는 것을 제외한다면, 사실 이 문제와 기본적으로 생각할 지점은 같았던 것 같다. 근데 케이스 분해가...

https://www.acmicpc.net/problem/11726