BOJ 1947 선물 전달

고민 많이 했었는데... 한 가지 사고에서 벗어나질 못하고 꽉 막혀있었다.
그래서 결국 질문게시판에서 어떤 분이 링크 해놓으신 사이트를 참조하게 되었는데,
완전 순열이란 것이 있었다... 그리고 점화식 설명이...아... 어떻게 접근해야 하는지 이해도 되고, 정말 감탄도 했는데, 동시에 어떻게 이런 생각을 할 수 있나...뭔가 자괴감도 들고.. 휴
일단 어떻게든 해보자.

완전 순열에 대해 간단히 설명하자면...
간단히 말하면 두 순열을 비교했을 때, 같은 위치에 같은 숫자가 없으면 두 순열은 완전순열 관계라고 할 수 있는데, 음 자세하고 정확한 정의는 내가 참조한 사이트를 참고하자.

일단 그래서 이 문제는 딱 완전순열의 개수가 몇개냐를 구하는 문제라고 할 수 있는데,

바로 점화식 접근 방법에 들어가면
n+2개의 수로 구성된의 수열이 있을 때, (그냥 1부터 n+2)까지로 하자.
문제처럼 n+2명의 사람들이 서로 선물을 나눠가진다고 할 때...
모든 경우를 두 가지 경우로 나눌 수 있다. 바로...

첫번째,
    1과 k가 서로의 선물을 나눠가졌다고 하면, 나머지 n명은 서로 선물을 나눠가지면 되는데(An), 1과 2, 3, 4...n+2까지 즉 n+1개의 (1, k)조합이 있으므로  (n+1)*An
(참고로, 1과 k의 경우만 생각하면 되는 이유는(2와 k, 3과 k..등등을 생각하지 않아도 되는 이유는)... 어떤 경우든 간에, 1과 k가 서로 선물을 교환한 경우, 1이 k의 선물을 받고, k는 1의 선물을 안 받는 경우.. 딱 이 2가지로 커버되기 때문이다.)


두번째,
    1이 k의 선물을 받고, k는 1이외의 사람에게서 선물을 받아야하는 경우, 이 경우는 1은 k의 선물을 받았으니, 나머지 n+1명이 서로 선물을 나눠가지면 되고, 이 경우도 (1, k)조합은 n+1개이므로 (n+1)*An+1 인 것인데... 여기서 좀 의문이 들었었다.
첫번째 경우는 1과 k가 서로 교환한 상태이니 나머지 사람들 n명끼리 나눠 갖는 경우인데, 
두번째 경우는 1이 k의 선물을 받았는데, 나머지 n+1명은 k의 선물이 아닌 1의 선물과 나머지를 나눠 가져야 하므로 An+1이라기에는 좀 문제가 있어 보였다. 분명 경우의 수가 더 많을 것이다... 실제로 해보니 더 많았는데.. 여기서 내가 놓치고 있던 점이 있었다.
바로 1을 제외한 나머지 사람들이 k의 선물이 아닌 1의 선물을 포함한 선물들을 나눠 갖게 되지만 결국은 똑같다. 왜냐하면 k는 1의 선물을 가지지 않은 것으로 가정했기 때문에, 결국 n+1명이 선물을 나눠 갖는 경우와 같은 것이다! 그래서 결론 : (n+1)*An+1 이게 맞다.

-> 추가 : 3달 정도 만에 다시 풀어봤는데, 두번째의 경우 내가 생각한 아이디어를 추가하자면,  1이 k의 선물을 받았으니 1은 k이외의 사람에게 선물을 줘야하고, k는 1이외의 사람에게 선물을 받아야 하는 상황이다. 즉 1과 k를 묶어서 선물을 가진 새로운 한 사람으로 생각할 수 있다! 그렇다면 n명일 때는 (1과 k를 한사람으로 묶었으므로) (n-1)*An-1 이 된다.
물론 n+2명을 기준으로 한다면 (n+1)*An+1 이다.


결국 점화식은...
    An+2 = (n+1)*An+1 + (n+1)*An

출처 및 더 쉽고 자세한 설명은 ... -> http://j1w2k3.tistory.com/667