[JS] 아방가르드 타일링

이전 3*n 타일링을 이해했다면?! 이해할만한 문제였다.

 

 

가장 중요한 포인트는 이것이다.

 

세로줄이 한개씩 늘어날때마다 얼만큼의 경우의 수를 찾아야 하는지를 알아야 한다.

 

 

편의상 f(1)을 1개를 만들 수 있는 경우의 수라고 생각해보자.

 

f(1) = 1

f(2) = 3

f(3) = 10

 

우리가 생각할 때 f(4)를 만드는 경우,

 

f(1) * f(3)

f(2) * f(2)

f(3) * f(1)

위 값들을 다 더하면 된다.. 라고 생각해도 될까? 정답은 아니다

 

 

위처럼 나눈다면 f(1) * f(1) * f(1) * f(1) 이런 경우까지 다 고려해야 하며 그중에서 중복되는 값들이 생길 수 있어 계산하기 매우 번거로워진다.

 

따라서 유니크 타일이란 개념을 도입하면 이를 조금 쉽게 생각할 수 있다.

 

 

유니크 타일이란 n개에서만 만들 수 있는 타일이라고 생각해보자. U(n)을 n개일때의 유니크 타일 개수라고 생각해보자.

 

예를 들어 U(3) 은 3개로만 만들 수 있는 타일의 개수이므로 5개가 나올 것이다.

 

 

 

위 예시에서 가로 3칸짜리 타일이 들어간 5개의 타일이 바로 3개일때의 유니크 타일이다. 나머지 타일은 세로기준 1개 + 2개 의 조합으로 만들 수 있기 때문이다.

 

 

따라서 우리가 지금까지 타일의 개수를 구한 것에 세로줄 한칸을 더할때 아래와 같이 생각할 수 있다.

 

f(4)를 마찬가지로 구한다고 생각하면

 

f(3) * U(1) + f(2) + U(2) + f(1) + U(3)이 될 것이다!!!

 

 

 

조금 쉽게 생각해서 오른쪽의 유니크 타일들로 고정해둔다고 생각하면 편하다.

 

 

즉, 우리가 f(n)을 구한다면

 

f(n-1) * U(1)  + f(n-2) * U(2) + ..... + f(1) * U(n-1) 을 구해주면 된다.

 

 

이때 U가 어떻게 나오는지 보면

 

U(1) = 1

U(2) = 2

U(3) = 5

U(4) = 2

U(5) = 2

U(6) = 4

...

 

위처럼 4이상부터는 2,2,4 가 반복되서 나오게 된다.

 

(위 부분은 직접 도형 6개까지 만들어보면 바로 이해가 될 것이다.)

 

 

하지만 dp의 개수가 1000000개라서 이를 그때그때 더하면 너무 비효율적이니 부분합을 구해둔 배열을 통해서 이를 해결하면 문제를 해결할 수 있다.

 

 

 

 

사실 스스로 100% 해결하지는 못한 문제였고 부분합 구하는 부분을 겨우 이해하여 풀 수 있는 문제였다.

 

 

function solution(n) {
    const dp = [1,1,3,10,23,62,170]
    const sum = [1,1,3,11,24,65,181]

    
    for (let i = 7 ; i <= n ; i++) {
        dp.push((dp[i-1] + dp[i-2]*2 + dp[i-3]*5 + sum[i-4]*2 + sum[i-5]*2 + sum[i-6] *4 ) % 1000000007)
        sum.push((dp[i] + sum[i-3]) % 1000000007)
        
    }
    return dp[n]
}