출처
https://www.acmicpc.net/problem/17358
문제
오늘은 즐거운 선린 축제날, 갑자기 폭우가 쏟아지기 시작했다! 상민이는 비에 실망한 학우들을 위해 실내에서도 할 수 있는 복불복 게임을 준비했다.
상민이는 N개의 컵에 N개의 서로 다른 음료를 담았다. 그러고는 아래와 같은 규칙에 따라 음료를 섞기로 했다.
- 1~N의 번호가 메겨진 컵을 오름차순으로 일렬로 배치한다.
- 어떤 두 컵을 골라 위치를 맞바꾼다. 이 작업을 N/2번 반복한다.
- 모든 컵은 정확히 한 번씩 위치가 바뀌어야 한다. 자기 자신과는 위치를 바꿀 수 없다.
이쯤 읽고 나니 왠지 컵이 배열되는 경우의 수가 몇 가지인지 궁금해야 할 것 같다. 이걸 구하지 않으면 지구가 멸망한다고 한다. 이 문제를 풀고 지구의 용사가 되자!
입력
첫째 줄에 음료의 개수 N이 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 105)
출력
컵이 배열되는 경우의 수를 출력한다. 수가 커질 수 있으므로 10^9+7로 나눈 나머지를 출력한다.
예제 입출력
알고리즘 분류
- 수학
- 조합론
➡️문제 분석
쉽게 예를 들어 1, 2, 3, 4, 5, 6번의 6개의 컵이 있다고 가정해보자.
1번 컵이랑 어느 컵의 위치를 바꿀지 5개의 경우의 수(2, 3, 4, 5, 6)가 있다.
1번과 6번을 택한다고 하면 남은 컵은 2, 3, 4, 5번 컵이 있다.
2번 컵이랑 어느 컵의 위치를 바꿀지 3개의 경우의 수(3, 4, 5)가 있다.
2번과 4번을 택한다고 하면 남은 컵은 자동으로 3번과 5번이 된다.
따라서 컵이 6개일 때의 경우의 수는 5 * 3 * 1 = 15가 된다.
이를 식으로 나타내면 (n-1) * (n-3) * (n-5)
즉, n개의 컵일 때 경우의 수는 (n-1) * ((n-1)-2) * ((n-1)-4) ... * 1 이다.
➡️코드(⭕)
N = int(input())
cnt = 1
while N: # N이 0 이하가 되는 순간 반복을 멈춤
cnt *= N-1 # 경우의 수를 계속 곱한다
N -= 2 # N에서 2씩 뺀다
print(cnt % 1000000007)
➡️코드 분석
-
음료의 개수 N을 입력 받는다. (N은 무조건 짝수여야 함)
-
while문을 이용해서 반복을 하면서 매 반복마다 음료 두 개를 택해서 위치를 바꾸므로 cnt와 N-1을 누적하여 곱해준다.
-
그 다음 n에서 2씩 빼고 n이 0 이하가 되는 순간 반복을 중단 하도록 한다.
-
cnt를 10^9 + 7로 나눈것의 나머지가 경우의 수가 된다.
➡️end
코테는 수학 능력이 정말 중요한 것 같다
규칙을 찾아서 공식을 유도하는 과정이 혼자하기엔 아직 많이 어렵다ㅠㅠ
