여사건을 이용한 경우의 수1 - 특정 수를 포함하는 부분집합 구하는 법

20214번: Binary Seating (acmicpc.net)

 

 

두 강의실 0번과 1번에 n명의 학생이 1/2의 확률로 선택하여 입장할때,

 

1번 강의실에서 모든 시험이 끝날 때까지 걸리는 시간의 기댓값을 구하는 문제

 

걸리는 시간을 X라고 한다면...?

 

예를 들어 학생이 5명이고 각각 t = 1,4,5,2,3 만큼 시험을 보고 떠난다고 할때,

 

가능한 X = 1,2,3,4,5이다.

 

그러므로 E(X) = 1*P(X = 1) + 2*P(X = 2) + 3*P(X = 3) + 4*P(X = 4) + 5*P(X = 5)

 

P(X = 1)은 어떻게 구할까?

 

t = 1인 학생이 1번 강의실에 들어간 경우 (1)

 

P(X = 2)는 어떻게 구할까?

 

t = 2인 학생이 1번 강의실에 들어간 경우 (2)

 

t = 1인 학생도 1번 강의실에 들어간 경우 (1,2)도 1분 뒤면 1인 학생 떠나고, 2분 뒤면 2인 학생 떠나니..

 

2분 뒤에 모든 학생이 떠난다

 

....

 

비슷하게 P(X = 5)는..

 

(5)

 

(4,5)

 

(3,4,5)

 

(2,3,4,5)

 

(1,2,3,4,5)

 

즉, P(X = t)가 되는 경우의 수는...

 

(T <= t인 T로 이루어진 부분집합의 개수)와 같다.

 

T = [t1,t2,t3,...,tn]일때, 이들로 부분집합을 만드는 방법은?

 

각각이 집합에 포함되냐, 포함안되냐이므로 2*2*2*2*...2 = 2^n가지

 

T의 원소는 서로 같을 수도 있는데 예를 들어 [1,1,2,2,2]라고 한다면..?

 

X = 2인 경우의 수는..

 

학생들은 서로 다르면서도 T = 2가 집합에 반드시 포함되어야 하므로, 3개의 2중 1개를 뽑는 경우 3C1

 

남은 4칸에는 1,1,2,2 각각이 들어가냐 안들어가냐니까, 2^4가지?

 

그래서 총 24가지??

 

근데 실제로는

 

2222 22 22 22 2 2

1 2

1 2

1 2

1 2

1 2

1 2

1 2 2

1 2 2

1 2 2

1 2 2

1 2 2

1 2 2

1 2 2 2

1 2 2 2

1 1 2

1 1 2

1 1 2

1 1 2 2

1 1 2 2

1 1 2 2

1 1 2 2 2

 

28가지 나오는데?

 

덜 나올줄 알았는데 더 많이 나오네

 

이렇게 차이가 나면 다른 시각을 가지고 접근해보자

 

"집합에 적어도 하나의 2가 들어가야한다"이므로 여사건을 이용해서 접근하면 명확하다.

 

= "전체 만들 수 있는 부분집합의 수" - "2가 하나도 안들어가 있는 부분집합의 수"

 

= 2^5 = 32가지 - "1로만 만들 수 있는 부분집합의 수"

 

 = 32 - 2**2=4 = 28가지

 

그래서 먼저 T를 오름차순으로 정렬하고...

 

t1 <= t2 <= t3 <= ... <= tn

 

ti < ti+1이 되는 순간, ti가 적어도 하나 들어가는 부분집합의 수를 구해야하므로,

 

(2**(ti까지 개수) - 2**(ti-1까지 개수))*ti를 누적해서 더하면 된다.

 

당연히 전체 경우의 수는 2**n가지

 

그래서 총 기댓값은 누적된 합을 2**n으로 나누면 된다.

 

예를 들어 [1,1,1,2,2,3,3,3]이라면...

 

처음에 x = 0으로 두고, x보다 작은 값의 개수 count = 0으로 둔 다음

 

i = 0일때, 0 < 1이므로, (2**(지금까지 센 원소 수 i) - 2**(0의 개수 count))*0 = 0

 

x = 1로 두고 count = i (0의 개수) = 0

 

i = 3일때, 1 < 2가 되므로, 지금까지 센 원소 수 i = 3이고 1보다 작은 값들의 개수는 count = 0이므로...

 

(2**3 - 2**0)*1 = 7

 

x = 2로 두고 count = i = 3(1의 개수)

 

i = 5일때, 2 < 3이므로, 지금까지 센 원소 수는 i = 5, 1의 개수는 count = 3

 

(2**5 - 2**3)*2 = 48

 

그리고 x = 3, count = 5로 두고

 

그리고 i = 8에서 끝나므로... 3의 경우도 세서 누적합 해줘야하는데, 그러지 못하게 되므로...

 

T에 미리 가장 큰 값보다 더 큰 값을 넣어주면 된다.

 

즉, 가능한 T는 최대 1000이므로 1001을 미리 끝에 append해주면

 

[1,1,1,2,2,3,3,3,1001]

 

i = 8에서 3 < 1001이므로, 지금까지 센 원소 수는 i = 8, 3보다 작은 원소 수는 count = 5

 

(2**8 - 2**5)*3으로 끝

 

#각각이 1/2로 선택하고 T <= t이면, X = t일때, X의 기댓값
#여사건을 이용한 특정 수가 적어도 하나 이상 포함된 부분집합의 개수
n = int(input())

t = list(map(int,input().split()))

#T를 정렬하고
t.sort()

t.append(1001)

x = 0
total = 0

count = 0

#a,a,a,a,...,a,b,b,b,b,...,b에서 b가 적어도 하나 포함된 부분집합의 개수
#전체 부분집합의 수 - a들로만 만든 부분집합의 수
#2**(a의 개수+b의 개수) - 2**(a의 개수)

#count = x보다 작은 값들의 개수
#i=처음부터 x까지의 개수
#x를 적어도 하나 포함하는 부분집합의 개수 = 2**(i) - 2**(count)
for i in range(n+1):

    if x < t[i]:
        
        total += (2**(i)-2**(count))*x
        x = t[i]
        count = i

print(total/(2**n))