17073번 - 나무 위의 빗물
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가 됩니다.
'트리의 루트 노드는 항상 리프 노드의 수보다 많은 개수의 물을 가진다.'혹은'리프 노드가 모두 물을 하나 이상 가질 수 있는 상황이 입력으로 주어진다'라는 조건이 추가돼야 할 것 같습니다.
문제에서 구하는 것은 각 노드의 물 양의 기댓값이 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입니다.
댓글을 작성하려면 로그인해야 합니다.
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가 됩니다.
'트리의 루트 노드는 항상 리프 노드의 수보다 많은 개수의 물을 가진다.'
혹은
'리프 노드가 모두 물을 하나 이상 가질 수 있는 상황이 입력으로 주어진다'
라는 조건이 추가돼야 할 것 같습니다.