백준 - 나무 위의 빗물

문제 설명

최초 루트 노드에 물이 존재하고 루트를 기점으로 물이 자식에게 분배된다.

그러면 기대하는 값(pi)이 0보다 큰 경우의 평균을 구하는 것이다.

i번 정점에 쌓인 물의 양의 기댓값을 Pi라 하자. 이때, Pi가 0보다 큰 정점들에 대해서 Pi들의 평균은 어느 정도가 될까?

생각한 아이디어

루트에서 부터 탐색하면서 자식에게 물의 값을 양도하도록 직접 구현했다. 하지만 FAIL

왜 Fail이 나는지 몰랐었다.

Pi가 0보다 큰 정점들에 대해서 Pi들의 평균 → pi가 0보다 큰 값인지 실제로 체크를 했다.

나의 구현에서는 root의 물의 양이 1일 때 하나의 정점에서만 pi>0 을 만족해서 물의 양도 :1, 총 점정 : 1로

1/1 = 1.0000000000 으로 출력했다. 그래서 FAIL이 난 것 같다.

리프노드가 곧 물의 이동이 멈출 때라는 것을 생각했지만 루트의 물의 양이 1이고 Leaf 노드가 2개이상일 때에는 pi>0 조건을 만족하는 정점은 1개라고 생각했다.

문제에서 수치적으로 Pi>0 큰 정점들에 대해서 라고 말해줬는데… 이상하다라고 생각했다.

기댓값이라는 사전적 정의로 보면 이러했다.

각 사건이 벌어졌을 때의 이득과 그 사건이 벌어질 확률을 곱한 것을 전체 사건에 대해 합한 값이다.

예를 들어, 주사위를 한 번 던졌을 때, 각 눈의 값이 나올 확률은 1/6이고, 주사위값의 기댓값은 각 눈의 값에 그 확률을 곱한 값의 합인

1⋅16+2⋅16+3⋅16+4⋅16+5⋅16+6⋅16=3.5

https://wikimedia.org/api/rest_v1/media/math/render/svg/68512c225071812574cdcd829b5c0175891d3d1a

그래서 문제에서 의도한 것은 전체 사건이 리프노드가 pi>0 이다라고 애기하는 것 같다…

풀이

 

  static List<Integer>[] adj;
	static final int ROOT = 1;

	/**
	 * 리프의 갯수대로 나노 먹을 것이다.
	 * 하지만 root의 물의 양이 1이라면 pi가 0보다 큰 정점은 leaf 개수가 아닌 1개 인데...?
	 * 음.. 평균은 하나의 리프에만 기댓값이 0보다 큰 1이 한개인데...?
	 * 그런데 pi가 0보다 큰 정점들에 대해서 수치적으로 0보다 큰 값이 무조건적으로 리프의 개수라고 말할 수 없지 않나
	 * 리프에 물이 고일 것이라고 기대하는 것이지 실제 리프마다 물이 있을거라는 그것이 없자나..
	 *
	 * 기댓값이 나올 수 있는 pi가 0이 아닐 거라는 것이 := 리프노드 인갑네..
	 */
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(reader.readLine());
		int n = Integer.parseInt(st.nextToken());
		int water = Integer.parseInt(st.nextToken());

		adj = new List[n + 1];
		for (int i = 1; i < n + 1; i++) {
			adj[i] = new ArrayList<>();
		}

		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(reader.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			adj[a].add(b);
			adj[b].add(a);
		}

		int leaf = 0;
		for (int i = 2; i < n + 1; i++) {
			if (adj[i].size() == 1)
				leaf++;
		}

		System.out.println(String.format("%.10f", (double)water / leaf));
	}