13976번 타일 채우기 2

정말 오래 걸렸다. 다른 타일 채우기 문제처럼 단순히 점화식 찾아서 그대로 dp로 풀면 될 줄 알았는데 안된다. 그게 바로 두달 전.

 

11444번 문제 풀면서 찾아봤던 행렬 계산을 통해 풀었다.

 

F(n) = 3*F(n-2) + 2{F(n-4) + F(n-6) + F(n-8) +........+ F(0)}

 

-> 이 식에서 n 대신 n-2를 대입

 

F(n-2) = 3*F(n-4) + 2{F(n-6) + F(n-8) + F(n-10) +........+ F(0)}

 

-> 두 식을 빼면

 

F(n)-F(n-2) = 3*F(n-2) - F(n-4)

 

-> F(n) = 4*F(n-2) - F(n-4)라는 식을 구할 수 있다.

 

이 식을 2차 행렬로 나타내서 풀면 된다.

 

c[i][j] = (c[i][j]+mod)%mod

-> mod 계산을 하다보면 계산값이 양수가 아닌 음수가 나오는 경우가 있다. 그것을 방지하기 위해 보통 mod값을 더해주고 나눈다고 한다.