점화식을 어떻게 세우셨는지는 잘 모르겠는데요.

n = 12일 때부터 답이 제대로 나오지 않네요. n이 12인 경우 답은 132입니다.

힌트를 몇 가지 드리자면.

처음에 a와 b를 뽑아놓습니다. (단 a와 b는 1보다는 크거나 같고 n보다는 작거나 같은 자연수)

(1) 이 둘 중 한 명을 고정시켜 놓습니다. 그림을 그려보시면 규칙을 찾으실 수 있으실 겁니다.

그러면 곱사건으로 해결하실 수 있겠지요?

이 문제에서 핵심은

(2) a와 b랑 악수하는 사건이랑 a와 c가 (단 c는 b와 같지 않은 사람) 악수하는 사건이랑은 별개의 사건이라는 겁니다.

a와 b가 악수하는 것과, a랑 c랑 악수하는 건 동시에 일어날 수 없거든요.

2가지 힌트를 드렸고요.. 거의 다 준거라 생각합니다.

그러면 한 가지 의문점이 드실 겁니다. 아니 왜 하필 a와 b를 미리 뽑아놓을까요?

당연한 이야기겠지만

a와 (a가 아닌 나머지 사람들)과 악수하는 가짓수들의 합 = 전체 가짓수 (즉 전체 사건)

이기 때문입니다.

a는 a가 아닌 임의의 누군가와는 악수를 해야 하고요. (문제의 특성상)

(3) 만약에 x칸 건너서 (단 x는 짝수) 있는 사람과 악수하는 경우는 없겠죠? 만약에 그런 경우에는

cross가 될 테니까요.

간단한 직관을 쓰시면 (3)도 쉽게 간파하실 수 있으실 겁니다.

감사합니다!!