[BOJ] 백준 17073. 나무 위의 빗물

문제

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

 

 

---

풀이

트리 문제입니다.

 

처음 아이디어는 트리를 순회해야한다는 생각에 트리를 dfs로 순회하며 리프 노드와 깊이를 구했습니다. 그래서 2의 (깊이) 승을 w에 나누어

W/(Math.pow(2, depth));

와 같이 식을 구성했습니다.

그런데 생각해보니, 수학에서 결합 법칙을 생각해보면, 모든 확률의 합은 1이기 때문에 기대 값은 W 그대로라는 것을 알 수 있습니다.

 

그래서 결과는 W / 리프 노드의 개수를 구한 값입니다.

 

 ArrayList에 입력을 받을 때 양방향 간선 트리에서 리프노드의 연결 값의 size는 1이라는 쉬운 특징이 있었습니다.  이를 통해 리프노드의 개수를 세어주었습니다.

 

추가로, 이 문제에서 부모 노드가 자식 노드보다 작다는 조건은 없다는 것을 주의해야합니다. 그래서 양방향으로 입력을 받아야 합니다.

---

소스코드

import java.util.ArrayList;
import java.util.Scanner;

public class B17073_나무위의빗물 {

    static int N,W;
    static ArrayList<Integer>[] list;
    static double avg;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        W = sc.nextInt();
        list = new ArrayList[N+1];
        for(int i = 0;i<N+1;i++){
            list[i] = new ArrayList<>();
        }
        for(int i = 0; i<N-1;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            list[a].add(b);
            list[b].add(a);
        }
        calculateAvg();
        System.out.println(avg);
    }

    static void calculateAvg(){
        int leafCount = 0;
        for(int i = 2;i<N+1; i++){
            if(list[i].size()==1) leafCount ++;
        }
        avg =(double)W/leafCount;
    }
}