[BOJ 22984, Python 3] 반짝반짝 2

https://www.acmicpc.net/problem/22984

22984번: 반짝반짝 2

알고리즘학회에서 gojib2002님의 풀이를 들었음

 

 

풀이

일단 일반 전구가 켜질 확률을 p[i]라고 둘 때, p[i] 확률로 불이 들어오는 i번째 전구의 기댓값은 p[i]인 것을 알 수 있습니다. 전구가 켜진다면 1개가 켜지고, 켜질 확률이 p[i]이므로 1 * p[i] = p[i]인 것입니다.

그래서 일반 전구가 켜지는 모든 기댓값은 p[1] + p[2] + p[3] + .... + p[n]입니다.

 

이제 추가 전구의 기댓값을 구해야 하는데, 문제에서 이웃한 두 전구 중 하나만이 켜졌을 때 불이 켜진다고 했으므로 이웃한 두 전구가 켜질 확률을 각각 p[i], p[j]라고 가정하면 추가 전구가 켜질 확률은 p[i] * (1 - p[j]) + (1 - p[i]) * p[j] 입니다.

 

이렇게 해서 전구 스트립에 불이 들어오는 전구 개수의 기댓값은 위 두 개의 내용을 더해주면 됩니다. 이것을 기댓값의 선형성이라고 부른다고 합니다.

 

 

코드

n = int(input())
p = [*map(float, input().split())]
print(sum(p) + sum([p[i] * (1 - p[i-1]) + (1 - p[i]) * p[i-1] for i in range(1, n)]))