P11726

[baekjoon-11726] 2×n 타일링

점화식

dp[1] = 1
dp[2] = 2
dp[n] = dp[n-1] + dp[n-2]

왜 이런 식이 성립하나?

2xn 크기의 직사각형은 2x(n-1) 크기의 직사각형을 채우고 2x1 타일을 채우는 방법의 수와, 2x(n-2) 크기의 직사각형을 채우고 1x2 타일 두 개를 채우는 방법의 수를 합친 것과 같다. 그 이상으로 더 자르면 대칭이거나, 이미 이전 단계의 경우의 수를 다 세었기 때문에 더 생각할 필요가 없다.