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

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

2×n 직사각형에서 (1,1) 위치를 생각해보면 이 위치는 1×2 타일로 덮이거나 2×1 타일로 덮입니다. 1×2로 덮이게 될 경우에는 (2, 1) 위치에는 반드시 1×2 타일이 와야하므로 2×(n-2) 타일을 까는 경우의 수가 됩니다.

2×1로 덮이게 될 경우에는 첫 열이 처리되고 이제 남은 2×(n-1) 타일을 까는 경우의 수가 됩니다. 즉

D[n] = D[n-1]+D[n-2]임을 알 수 있습니다.

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