zzaibean   1년 전

5 2

5 3

3 4

2 1

1 3

입력이 위와 같다면
가능한 최종적인 상황은 다음과 같습니다.

- 노드 2가 물을 2개 갖고 있는 경우
- 노드 4가 물을 2개 갖고 있는 경우
- 노드 5가 물을 2개 갖고 있는 경우
- 노드 2, 4가 물을 1개씩 갖고있는 경우
- 노드 2, 5가 물을 1개씩 갖고있는 경우
- 노드 4, 5가 물을 1개씩 갖고있는 경우

문제의 조건대로라면 물을 1개 이상 갖고 있는 노드의 평균 물 보유량을 구하는 것이기 때문에
위의 상황에서 평균 물 보유량은 현재 정답으로 인정되는 0.666667이 될 수 없습니다.

최종 상황에서 평균 물 보유량은 1 혹은 2가 됩니다.

'트리의 루트 노드는 항상 리프 노드의 수보다 많은 개수의 물을 가진다.'
혹은
'리프 노드가 모두 물을 하나 이상 가질 수 있는 상황이 입력으로 주어진다'

라는 조건이 추가돼야 할 것 같습니다.

kiwiyou   1년 전

문제에서 구하는 것은 각 노드의 물 양의 기댓값이 0보다 큰 노드에 대해서 기댓값의 평균입니다.

제시하신 여섯 경우가 전부이고 확률이 모두 같으므로,

- 노드 2의 물 양의 기댓값 = (2 + 1 + 1) / 6 = 2/3

- 노드 4의 물 양의 기댓값 = (2 + 1 + 1) / 6 = 2/3

- 노드 5의 물 양의 기댓값 = (2 + 1 + 1) / 6 = 2/3

세 기댓값의 평균은 (2/3 + 2/3 + 2/3) / 3 = 2/3입니다.

댓글을 작성하려면 로그인해야 합니다.