[BOJ] 2133번: 타일 채우기

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

적절한 점화식을 찾아내야하는데, 썩 쉽지는 않습니다. 3×n을 채우는 횟수만을 D[n]으로 점화식을 쓰려고 하면 적절한 점화식을 떠올리기가 힘듭니다. 대신에

D1[n] : 3×n

D2[n] : 3×(n-1)+1 (3×n에서 (1,1), (1,2)가 사용불가능한 형태)

D3[n] : 3×(n-1)+2 (3×n에서 (1,1)이 사용불가능한 형태)

라고 정의를 한다면, 경우의 수를 잘 나눠보면

D1[n] = D3[n]+D2[n-1]+D1[n-2]

D2[n] = D1[n-1]+D3[n-1]

D3[n] = D2[n-1]

이라는 점화식을 얻어낼 수 있고 이것들을 채워나가면 됩니다.

https://github.com/encrypted-def/BOJ/blob/master/2133.cpp