백준 11726, 11727

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

11726번: 2×n 타일링

점화식 d[n] = d[n - 1] + d[n - 2];

보통 설명은 이렇게 되어 있다. 

n 번째 타일링 경우의 수 = n - 1 번째 타일링 경우의 수 + n - 2 번째 타일링 경우의 수;

 

이게 이해가 되지 않아서 1시간동안 삽질한 끝에 드디어 이해했다...

나는 계속 n 이 증가하는 방향에서만 생각했었고, n - 1, n - 2 에서 한칸과 두칸 비는 공간에 대한 인식을 전혀 하지 않았었기 때문이었다. (개멍청)

 

저 점화식을 좀 더 자세히 설명하면 이렇게 된다.

N 번째 타일링 경우의 수 = 마지막 타일링이 세로 타일로 끝나는 경우 + 마지막 타일링이 가로 타일로 끝나는 경우;

ex) d[3] = d[2]{ ||, = } + d[1]{ | } = || + |, = + |, | + =;

 

이것을 이해했으면 11727 번 문제는 어처구니가 없을정도로 쉬운 문제가 된다.

d[n] (n 번째 타일링 경우의 수)

    = d[n - 1] + d[n - 2] * 2

    = 마지막이 2 * 1 타일 * 1 개로 끝남 + 마지막이 1 * 2 타일 * 2 개로 끝남 + 마지막이 2 * 2 타일 * 1 개로 끝남