확률. 쿠폰 문제.

ICPC 문제 중 쿠폰 이라는 문제가 있다. 

확률에 대한 개념이 별로 없어서 안 건들일려고 했는데, 해답을 보니.. 재밌는 문제인것 같다.

문제는 이렇다. 한 치킨집에서 1~N개 종류의 쿠폰을 나눠주는데, 1부터 N 까지 모든 종류의 쿠폰을 한장씩 모으면 황금 치킨을 준다. 한번 먹을때마다 임의의 쿠폰을 1개씩 받는다고 하면, 내가 황금 치킨을 먹기 위해서는 평균적으로 몇번의 주문을 시켜야하나?

우선, 각각 쿠폰을 받을 확률이 1/N 이라고 생각했을 때, 식을 전개해보면,

처음에는 아무 쿠폰이나 받아도됨 -> 처음받은걸 또받음                    ->   처음 받은걸 또받음

                                                           |-> 처음받은것 말고 나머지를 받음  

                                       |->처음받은것 말고 나머지를 받음     ->   두번째 받은거나 첫번째 받은걸 받음.

                                           |->  첫번째나 두번째받은것 말고 나머지를 받음  

이런식으로 정리해 나가다 보면. 답을 찾을수.... 없음. ㅋ 

계속 이런식으로 고민하다가 결국 구글에서 솔루션을 찾아봄.

---

문제의 핵심은 각각을 나눠서 생각하는 것이다. 

잘 생각해보면, 처음에 아무 쿠폰이나 받고 -> 처음과 다른 쿠폰을 받기 위해 계속 주문하고  -> 앞서 받은 두번과 다른 종류의 쿠폰을 받기 위해 계속 주문하고 -> ...  

이렇게 부분을 나눈 process로 생각 할 수 있기 때문에, 이때 총 주문한 횟수의 평균을 구하면 된다.

잘 생각해보면 각각의 부분은 앞 부분의 평균적 영향을 받기 때문에.

처음에 쿠폰을 받기 위한 평균적 주문 횟수 + 처음과 다른 종류의 아무 쿠폰을 받기 위한 평균적 주문 횟수 + 처음과 두번째 와 다른 종류의 쿠폰을 받기 위한 평균적 주문 횟수 + ...

라고 생각할 수 있다. 원하는 쿠폰을 뽑을 확률을 p 라고하고, 그 확률을 뽑기위한 평균적 주문횟수를 func(p)라고 했을때.

위 식을 정리하면 func(1) + func(N-1/N) + func(N-2/N) + func(N-3/N) + ... 가 된다.

그렇기 때문에 func(p)를 구하면 된다.

한번에 원하는 걸 뽑을 확률 = p, 두번에 원하는걸 뽑을 확률 = (1-p) * p, 세번에 원하는걸 뽑을 확률 = (1-p) * (1-p) * p로 나타낼 수 있다. 

 이를 계산하면, 

위에식에서 아래 식을 빼면,

  그러므로 func(p) = 1/p이다. 

그렇기 때문에 이 문제는 1 + N/(N-1) + N/(N-2) + N/(N-3) + ... + N 이 된다.