[BOJ 24270] 백준 24268번 - 미니 버킷 리스트

		Hello, BOJ 2022! 풀이
A		[BOJ 24268] 2022는 무엇이 특별할까?
C		[BOJ 24270] 미니 버킷 리스트

1. 문제

$24270$. 미니 버킷 리스트 (Hello, BOJ 2022! C번)

백준 24270번 - 미니 버킷 리스트 (https://www.acmicpc.net/problem/24270)

2. 풀이

$N=2, K=10$
$S_1=2,\, S_2=3$

다음의 하나의 예시를 가정한다.

이는 $10$개 중에 $2$개를 한 그룹으로 묶고, $3$개를 다른 한 그룹으로 묶는 경우의 수를 구함을 의미한다. 나머지 $5$개는 서로 구분되지 않으며, $2$개 $3$개 묶음을 어떻게 하는지에 따라서 위치가 달라진다.

여기서 그룹이 되지 않은 나머지 각각이 위치할 수 있는 곳은 그룹의 사이사이임을 알 수 있다. (서로서로는 구분되지 않고 어떠한 그룹의 앞인지 뒤인지에 따라서 구분되기 때문에)

그룹이 $N$개이므로 그룹이 아닌 나머지 하나하나가 위치할 수 있는 곳은 $N+1$곳이 있다. 나머지는 $K$에서 $S(1\sim N)$을 모두 더한 값을 뺀 값이고, 이를 rest라고 둔다.

그러면 $N+1$곳에 rest개를 구분없이 배정하는 작업이므로 ${N+1}H{rest}$를 구하면 된다. 이는 $H$와 $C$ 연관 공식에 의해 ${N+rest}C{rest}$이다. 또한, 전체 그룹의 일 순서가 바뀌는 경우는 $N!$이다. 이를 이전 조합식에 곱하면 원하는 출력값이다.

\[\begin{aligned} N!& \times _{N+1}H_{rest} \\ \\ =& \,N! \times _{N+rest}C_{rest} \\ \\ =& \,N! \times ((N+rest)! / (N! \times rest!)) \\ \\ =& \,(N+rest)! / rest! \\ \\ =& \,(rest+1)\times(rest+2)\times(rest+3)\times \\ \\ &... \times(N+rest-1)\times(N+rest) \end{aligned}\]

$rest+1$부터 $N+rest$까지는 총 $N$개의 곱연산이다. $N$의 최대값은 $500,000$ 이므로 시간 내에 연산이 가능하다.

3. 채점 결과

4. 회고

\(N! \times _{N+1}H_{rest}\) 식을 정리하지 않고 팩토리얼 계산으로 시도하는 경우, $K\leq 10^9$여서 $rest$값이 $10^9$에 가까운 값도 나올 수 있어, $(N+rest)!$이나 $rest!$을 구할 수 없다. 이로 인해 WA와 RTE를 받았다.

5. 코드