1720 타일 코드

2*N의 타일을 2*1, 2*2 의 조각으로 채울 때, 좌우 대칭이 되는 경우를 제외한 나머지 경우를 구하는 문제이다.

우선 좌우 대칭을 고려하지 않고 경우의 수를 측정하면
f(n) = f(n-1) + 2*f(n-2) 가 된다.

좌우 대칭을 제외 하는것은,
f(n) 에서 좌우대칭이 되지 않는 조각의 수를 뺀것을 2로 나누어 주고,
다시 그 값을 f(n) 에서 빼주면 된다.

좌우 대칭이 되지 않는 조각의 수는 n이 짝수이면 f(n/2 + 1) 홀수이면 f((n-1)/2)  로 구할 수 있다.

왜 저렇게 풀리는지는 정확히 모르겠다.

소스