문제

오늘은 즐거운 선린 축제날, 갑자기 폭우가 쏟아지기 시작했다! 상민이는 비에 실망한 학우들을 위해 실내에서도 할 수 있는 복불복 게임을 준비했다.

상민이는 N개의 컵에 N개의 서로 다른 음료를 담았다. 그러고는 아래와 같은 규칙에 따라 음료를 섞기로 했다.

1~N의 번호가 메겨진 컵을 오름차순으로 일렬로 배치한다.
어떤 두 컵을 골라 위치를 맞바꾼다. 이 작업을 N/2번 반복한다.
모든 컵은 정확히 한 번씩 위치가 바뀌어야 한다. 자기 자신과는 위치를 바꿀 수 없다.
이쯤 읽고 나니 왠지 컵이 배열되는 경우의 수가 몇 가지인지 궁금해야 할 것 같다. 이걸 구하지 않으면 지구가 멸망한다고 한다. 이 문제를 풀고 지구의 용사가 되자!

입력

첫째 줄에 음료의 개수 N이 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 10^5)

출력

컵이 배열되는 경우의 수를 출력한다. 수가 커질 수 있으므로 109+7로 나눈 나머지를 출력한다.

예제 입력

4

예제 출력

3

내가 했던 풀이 방법

N이 4개, 6개...일 때를 생각해서 규칙을 찾으면 된다.

N이 2개일 때는 무조건 1이다. 서로 위치를 바꿔주는 것 밖에 없다. 그러므로 count를 1로 두었다.
N이 4개일 때 1번 컵을 바꿀 위치를 선택하는 경우의 수는 3개이다. 위치를 바꿀 수 있는 경우는 2번 뿐이므로 바뀌지 않은 컵들의 위치를 바꿔준다. 즉, N이 4일 때 경우의 수는 1×3이다.
N이 6개일 때 1번 컵을 바꿀 위치를 선택하는 경우의 수는 5개이다. 바뀌지 않은 컵 중 하나의 컵이 바꿀 수 있는 위치의 경우의 수는 3개이다. 위치를 바꿀 수 있는 경우는 3번 뿐이므로 바뀌지 않은 컵들의 위치를 바꿔주어야 한다. 즉, N이 6일 때 경우의 수는 5×3=15이다.

이런 방법을 반복하다보면, (N-2개의 경우의 수)×(N-1)이라는 식을 얻을 수 있게 된다.

코드

var fs = require('fs');
let N = fs.readFileSync(0, 'utf-8').toString().trim();
N = BigInt(N);

let count = 1n;
for (let i = 2n; i <= N; i += 2n) {
  count = (i - 1n) * count;
}

count %= 1000000007n;

console.log(count.toString());

회고

경우의 수를 찾으면 됐는데 쓸데없이 확률을 생각해서 시간을 쓴 문제.... 뇌를 비우고 다시 생각하니 금방 풀이됐다. 수학 문제가 제일 어렵다. 수포자는 울어요.