[Programmers] Lv3 산 모양 타일링 [작성 중]

산 모양 타일링

문제 해석

타일링 문제는 워낙 많이 알려져있어 문제를 보면 DP 를 이용하는 패턴이라는 것을 짐작할 수 있다. 다만 이전의 문제들과 다르게 사각형 타일링이 아닌 삼각형 타일링이라는것이 특이한 점이다.

주어진 타일은 위 그림의 패턴들을 사용하여 채울 수 있으며 좌측 상단부터 Z 형태로 1,2,3,4 번 타일이라고 해두고 시작하자.

문제 풀이

가장 단순한 n = 1 인 경우를 생각해보면 3개의 삼각형이 순서대로 나열되어 있고, 가운데 삼각형 위에 삼각형이 올라간 경우와 올라가지 않은 경우가 있다. 이 경우 삼각형을 채우는 패턴은 아래와 같은 그림으로 표현할 수 있다.

top 이 없는 경우

1. 3개의 정삼각형으로 채우는 경우
2. 좌측 정삼각형 하나만 정삼각형으로 채우고, 3번 마름모로 채우는 경우
3. 좌측 두개의 정삼각형을 2번 마름모로 채우고, 남은 우측을 정삼각형으로 채우는 경우

top이 있는 경우

1. 네개의 정삼각형으로 채우는 경우
2. top을 정삼각형으로 채우고 하단 좌측을 정삼각형으로, 남은 우측을 3번 마름모로 채우는 경우
3. top을 정삼각형으로 채우고 하단 좌측 두개의 삼각형을 2번 마름모로 채우고, 남은 우측을 정삼각형으로 채우는 경우
4. top과 top의 하단 삼각형을 4번 마름모로 채우고, 남은 두 부분을 정삼각형으로 채우는 경우

이제 n = 2 인 경우, 그리고 tops = [0, 1] 인 경우를 생각해보자