[프로그래머스] 아방가르드 타일링 (파이썬)

0. 문제 설명

아방가르드 타일링 문제 설명

문제는 간단하게 말해서,

왼쪽 도형 세개를 이용하여 높이가 3이고 넓이가 n 인 사각형을 빈틈없이 채울 수 있는 가짓수를 찾아내는 문제이다.

 

문제는 간단하지만 풀이 과정은 너무 험난했다.

실력이 많이 부족한걸수도 있고, 자랑스러운 걸수도 있고! 무려 2틀 동안 끙끙대며 풀었던 아방가르드 타일링 문제에 대한 과정과 풀이를 설명하려 한다.

 

우선,

다른 타일링 문제들과 같이 Dynamic Programming으로 접근해야 한다는 것은 느낌적으로 알았다.

 

첫 날은 그 점화식을 세우기 위해서 끙끙대며 점화식을 나름 만들어보고 풀어보았지만, 맞지 않았다. 😥

둘째 날 부터, 무작정 점화식을 세우는 것보다 조금만 더 차분히 그려가며 접근해보기로 하였다.

 

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

프로그래머스

 

1. 타일링 규칙 찾아보기

 

이제 부터 n = 1, 2, 3, 4, 5 일때, 어떤 타일을 가질 수 있는지 그려보며 규칙을 찾아낼것이다.

---

n=1 일 때와 n=2일 때를 살펴보자!

 

n 이 1 일 경우와 2일 경우 직관적이지만 우리는 숨은 뜻을 알아내야 한다.

 

n=1, n=2일 떄

 

바로 n이 1일경우 생전 처음 보는 타일은 하나이고 n 이 2일경우 생전 처음 보는 타일은 두개이다!

n=2 일 때 보이는 마지막 파란색 두개의 타일은 앞서 본 n=1일 경우의 타일을 조합하여 만들어 냈다.

---

그럼 n=3 일 때를 살펴보자

n=3 아방가르드 타일링

우선 생전 처음 보는 타일은 5개이다! 그리고 뒤에 다른 타일들은 사실 앞에서 본 n=1일 경우와 n=2일 경우 봤었던 타일로 조합하여 만들어 낸 것이다.

(주의: 파랑색, 연두색 조각 저번에 봤는데요? 라고 생각하면 안된다. 여기서 처음 보는 타일이란 n=x 일 경우 빈 공간 없이 만들어내는 문양 중에 n=y (0< y < x) 에서 보지 못했던 패턴이여야 한다.)

따라서 n=3 일때 만들 수 있는 타일의 총 개수는,

n=3일 때만 만들 수 있는 새로운 조합 + 

n=2일 때만 만들 수 있는 새로운 조합 x 나머지 한칸에 올 수 있는 경우의 수 + 

n=1일 때만 만들 수 있는 새로운 조합 x 나머지 두칸에 올 수 있는 경우의 수 

따라서 (n이 3일 경우) = 5 + 2 * 1 + 1 * 3 = 10 이다. 

---

자, n=4일 때를 보자

n=4 아방가르드 타일링

이 때 보이는 새로운 타일은 2개이다!

따라서 n=4 일때 만들수 있는 타일 총 개수는,

n=4일 때만 만들 수 있는 새로운 조합 +

n=3일 때만 만들 수 있는 새로운 조합 x 나머지 한칸에 올 수 있는 경우의 수 +

n=2일 때만 만들 수 있는 새로운 조합 x 나머지 두칸에 올 수 있는 경우의 수 + 

n=1일 때만 만들 수 있는 새로운 조합 x 나머지 세칸에 올 수 있는 경우의 수이다.
따라서, (n이 4일 경우) = 2 + 5 * 1 + 2 * 3 + 1 * 10 = 23 이다.

---

지치면 안된다! n=5일 때를 보자

 

n=5 아방가르드 타일링

 

새롭게 만들어 낼 수 있는 타일은 또 2개이다.

따라서 n=5일때 만들 수 있는 타일 총 개수는,

n=5일 때만 만들 수 있는 새로운 조합 +

n=4일 때만 만들 수 있는 새로운 조합 x 나머지 한칸에 올 수 있는 경우의 수 +

n=3일 때만 만들 수 있는 새로운 조합 x 나머지 두칸에 올 수 있는 경우의 수 +

n=2일 때만 만들 수 있는 새로운 조합 x 나머지 세칸에 올 수 있는 경우의 수 + 

n=1일 때만 만들 수 있는 새로운 조합 x 나머지 네칸에 올 수 있는 경우의 수이다.

즉, (n이 5일 경우) = 2 + 2 * 1 + 5 * 3 + 2 * 10 + 1 * 23 = 62 이다.

---

마지막으로 n=6일 때를 보자!

n=6 아방가르드 타일링

새롭게 만들어 낼 수 있는 타일은 4개 이다.

따라서 n=6일때 만들 수 있는 타일 총 개수는,

n=6일 때만 만들 수 있는 새로운 조합 +

n=5일 때만 만들 수 있는 새로운 조합 x 나머지 한칸에 올 수 있는 경우의 수 +

n=4일 때만 만들 수 있는 새로운 조합 x 나머지 두칸에 올 수 있는 경우의 수 +

n=3일 때만 만들 수 있는 새로운 조합 x 나머지 세칸에 올 수 있는 경우의 수 +

n=2일 때만 만들 수 있는 새로운 조합 x 나머지 네칸에 올 수 있는 경우의 수 + 

n=1일 때만 만들 수 있는 새로운 조합 x 나머지 다섯칸에 올 수 있는 경우의 수이다.

즉, (n이 6일 경우) = 4 + 2 * 1 + 2 * 3 + 5 * 10 + 2 * 23 + 1 * 62 = 170 이다.

---

이 다음 부터는 새롭게 만들어 낼 수 있는 타일들이 일정한 규칙을 갖게 된다.

n=7, n=8, n=9 아방가르드 타일링

예를들어 n=7 일경우, 8일경우 9일경우는 각각 4, 5, 6 일 경우보다 파란색 사각형을 늘려준 경우밖에 없다.

아하! 이제 드디어 일정한 규칙을 찾았기에 점화식을 세울 수 있다.

2. 점화식 세우기

DP(x) = DP(x-1) + 2*DP(x-2) + 5*DP(x-3) + 2*DP(x-4) + 2*DP(x-5) + 4*DP(x-6)
              + 2*DP(x-7) + 2*DP(x-8) + 4*DP(x-9) + ...

이란 식이 나오게 된다. x-3 이후 부터는 2, 2, 4 가 반복이 된다는 것을 알 수 있다.

 

중학교? 고등학교? 때 배운 점화식을 정리하는 방법을 떠올려 본다면 (하하..)

반복이 세개의 항으로 이루어지기 때문에 DP(x+3) 에서 DP(x) 를 빼보자.

점화식 정리

그러면 이처럼

 

DP(x) = DP(x-1) + 2*DP(x-2) + 6*DP(x-3) + DP(x-4) - DP(x-6)

 

의 아름다운 수식이 나온다. 그리고 이 수식을 그대로 코드에 반영을 하였다.

3. 코드

MOD = 1_000_000_007

def solution(n):
    dp = [0, 1, 3, 10, 23, 62, 170]
    
    if n < 7:
        return dp[n]
    
    for i in range(7, n+1):
        x = (dp[-1] + 2 * dp[-2] + 6 * dp[-3] + dp[-4] - dp[-6]) % MOD
        dp = dp[1:] + [x]

    return dp[-1]

4. 후기

아름다운 문제였다. 규칙을 찾아내는 통찰력을 요구하며, 그 규칙을 찾아내기까지의 끈기와 노력까지 본다.

 

다른 풀이들을 찾아보니 다 비슷하게 접근을 하였다. 대부분이 matrix를 사용하였는데 근본적인 접근법은 나와 전혀 다름이 없었다.

 

어려움을 겪는 다른 분들에게 작은 도움이 되길 바라며! 이만 글 마치겠습니다~