[BOJ] 11727번: 2×n 타일링 2

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

11726번 문제와 비교했을 때 2×2 타일이 하나 추가되었습니다. 그렇지만 풀이 자체는 비슷하게 점화식을 이끌어내면 됩니다. 2×n 직사각형에서 (1,1) 위치를 생각해보면 이 위치는 1×2 타일로 덮이거나 2×1 타일로 덮이거나 2×2 타일로 덮입니다. 1×2로 덮이게 될 경우에는 (2, 1) 위치에는 반드시 1×2 타일이 와야하므로 2×(n-2) 타일을 까는 경우의 수가 됩니다.

2×1로 덮이게 될 경우에는 첫 열이 처리되고 이제 남은 2×(n-1) 타일을 까는 경우의 수가 됩니다. 마지막으로 2×2로 덮이게 될 경우에는 두 열이 처리되고 남은 2×(n-2) 타일을 까는 경우의 수가 됩니다.그러므로 D[n] = D[n-1]+2*D[n-2]임을 알 수 있습니다.

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