BOJ 25197. 합주단 곰곰

▣ 문제 출처  ─  제1 회 곰곰컵 G번 문제

▣ 알고리즘 분류  ─  수학 / 확률론(기댓값의 선형성) / 조합론(더블 카운팅)

▣ solved.ac 기준 난이도  ─  Gold II (개인적으로는 골1 정도라고 생각한다.)

 

 

문제 링크: https://www.acmicpc.net/problem/25197

 

  $N$명의 사람들이 서로 다른 $K$개의 조에 균등한 확률로 랜덤하게 나뉘어 들어간다. 각 조에서 모든 쌍이 식사를 한 번씩 한다고 할 때, 전체 식사 횟수의 기댓값은 얼마일까?

 

  일단 $N$명의 사람들이 $K$개의 조에 들어가는 모든 경우의 수는 $K^N$가지인 걸 알고 있으므로 총 식사 횟수의 합을 구할 수 있으면 되는데, 모든 경우에 대해 일일이 식사 횟수를 구하는 건 범위상 당연히 불가능하다. 그런데 어차피 합만 필요하기에, 굳이 각각의 경우를 모두 봐 가며 구할 필요가 없다. 이런 경우, 예전 글에서 설명한 적 있는 더블 카운팅(Double Counting)을 이용해 다른 관점에서 접근해 보는 전략이 유효하다.

 

  그렇다면 어떤 관점을 이용해야 할까? 아무래도 가장 먼저 떠오르는 것은 조원의 수일 것이다. 각 조에서의 총 식사 횟수는 조원의 수로 표현되니까…. 그러니 조원의 수를 기준으로 식사 횟수를 세어 보자. 모든 경우를 통틀어 조원이 $t$명인 조의 개수는 $K$개의 조 중 한 조를 고른 뒤$(=K)$, $N$명 중 해당 조에 포함될 $t$명을 고르고$(=\binom Nt)$, 나머지 $N-t$명을 $K-1$개의 조에 배분$(=(K-1)^{N-t})$하는 경우의 수와 같다. 한편 조원이 $t$명인 조에서의 식사 횟수는 $\dfrac{t(t-1)}{2}$번이고 $t$는 $2$부터 $N$까지 가능하므로($t=1$이면 식사가 이루어지지 않으므로 고려하지 않아도 된다), 전체 식사 횟수 $T$는 다음과 같다.

$$\therefore\, T = \sum_{t=2}^N K\binom Nt (K-1)^{N-t}\frac{t(t-1)}{2}$$

 

  뭔가 괴상망측한 식이 나왔는데… 어라! 가만히 보니, 뭔가 이항정리 식과 모양이 비슷하지 않은가? 이항정리에 의해

$$(x+y)^N = \sum_{t=0}^N \binom Nt x^t y^{N-t}$$

이고, 이 식은 모든 실수 $x,\, y$에 대한 항등식이므로 양변을 $x$에 대해 편미분하면

$$N(x+y)^{N-1} = \sum_{t=1}^N \binom Nt x^{t-1} y^{N-t} t$$

가 되고, 한 번 더 양변을 $x$에 대해 편미분하면

$$N(N-1)(x+y)^{N-2} = \sum_{t=2}^N \binom Nt x^{t-2} y^{N-t} t(t-1)$$

가 된다. 여기서 $x=1,\, y=K-1$을 대입해 주면…

$$\begin{aligned} \therefore\, \sum_{t=2}^N \binom Nt (K-1)^{N-t} t(t-1) &= N(N-1)(1+K-1)^{N-2} \\ &\color{orangered}{= N(N-1)K^{N-2}} \end{aligned}​$$

와! 길었던 식이 아주 단순해진 걸 볼 수 있다. 따라서

$$\begin{aligned} T &= \frac{K}{2}\sum_{t=2}^N \binom Nt (K-1)^{N-t}t(t-1) \\ &= \frac{K}{2}N(N-1)K^{N-2} = \frac{1}{2}N(N-1)K^{N-1} \end{aligned}​$$

로 정리되고, 우리가 찾고자 한 식사 횟수의 기댓값은 이를 전체 경우의 수 $K^N$으로 나눈

$$\frac{T}{K^N} = \frac{N(N-1)}{2K}$$

가 된다! 따라서 $N$과 $K$가 입력되면 그냥 저 값을 출력해 주면 된다. 아래는 그를 구현한 코드다. (사실 구현이랄 것도 없지만…)

#include <stdio.h>

int main()
{
	int N, K;
	scanf("%d%d", &N, &K);
	printf("%f", N*(N-1) / (2.0*K));
	return 0;
}

 

 

---

 

 

  나는 곰곰컵에 참여했을 당시 위 풀이로 풀었었는데, 막상 최종 답이 너무 간단한 걸 보니 이런 무식한(?) 방법 말고 간결한 풀이가 있지 않을까 하는 느낌이 들었다. 대회가 끝나고 좀 더 고민을 해 보니, 기댓값의 선형성을 이용하는 간단한 풀이가 있었다.

 

  $N$명의 사람 중 $i$번 사람과 $j$번 사람이 식사를 하면 $1$, 안 하면 $0$의 값을 가지는 이산확률변수 $X_{(i,\, j)}$를 생각하자$(i < j)$. 그러면 전체 식사 횟수 $X$는

$$X = \sum_{1 \le i < j \le N} X_{(i,\, j)}$$

로 나타낼 수 있다. 이때 기댓값의 선형성에 의해 $X$의 기댓값 $E[X]$는

$$E[X] = \sum_{1 \le i < j \le N} E[X_{(i,\, j)}]$$

가 되는데, 여기서 각각의 확률변수 $X_{(i,\, j)}$는 균등하므로 $E[X_{(i,\, j)}]$가 모두 같고, 그 값은 $\dfrac{1}{K}$이다($\because$ 임의의 두 사람이 식사할 확률은 곧 두 사람이 $K$개의 조 중 같은 조에 들어갈 확률인 $\dfrac{1}{K}$와 같다). 이때 $X_{(i,\, j)}$는 총 $\dfrac{N(N-1)}{2}$개이므로…

$$\therefore\, E[X] = \frac{N(N-1)}{2K}$$

 

아까와 같은 결과가 훨씬 간단한 과정을 통해 나오는 걸 확인할 수 있다. (시무룩...)

 

 

그래도, 어찌 됐든 대회 중에 문제를 풀었으면 그만 아니겠는가…!