백준 17073 나무 위의 빗물

 

 

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

 

#include <iostream>
#include <vector>

using namespace std;

int esize[500001];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cout << fixed;
    cout.precision(6);

    int n, w;

    cin >> n >> w;


    for (int i = 0; i < n - 1; i++) {
        int u, v;

        cin >> u >> v;

        esize[u]++;
        esize[v]++;

    }

    double leaf = 0;

    for (int i = 2; i <= n; i++) {
        if (esize[i] == 1) {
            leaf++;
        }
    }


    cout << w / leaf;








    return 0;
}

 트리 문제이다.

 루트 노드(1)에서 물을 흘려보내 물이 더 이상 흐르지 않을 때 물의 양이 0보다 큰 각 노드에 대한 물의 양의 기댓값을 구하는 문제이다. 

 

풀이

물이 더 이상 흐르지 않을 때에는 모든 물이 leaf node에 있을 것이고, 

• 물을 가지고 있으며, 자식 정점이 있다면 자식 정점 중 하나를 골라 물을 1 준다. 자식 정점이 여러 개라면 동일한 확률로 그 중 하나를 고른다.

 해당 조건에 의해 부모 노드에서 자식 노드를 선택할 확률은 같으므로 해당 트리의 leaf node를 구한 후 전체 물의 양에서 나누어 준 값이 정답이다. 즉, 이 문제의 핵심은 edge가 주어졌을 때 트리의 leaf node의 수를 구하는 것이다.

    for (int i = 0; i < n - 1; i++) {
        int u, v;

        cin >> u >> v;

        esize[u]++;
        esize[v]++;

    }

    double leaf = 0;

    for (int i = 2; i <= n; i++) {
        if (esize[i] == 1) {
            leaf++;
        }
    }

 

 edge를 입력받을 때 마다 해당 vertex와 연결된 선의 수를 더하여 계산해준다. 이후 2번 vertex부터(1번은 문제의 조건에 의해 root이므로) edge의 개수가 1인 것이 leaf node이므로 계산해준다.(조건에서 n>=2이므로 1번 노드만 존재하는 경우는 고려하지 않는다.)

 

 이후 w/leaf를 출력하면 된다.

 

ps) c++는 유효숫자에 대해 과학적 표기법을 사용하기 때문에 소수점의 개수를 제한해주어야 한다.

 

    cout << fixed;
    cout.precision(6);

 

문제에서 정답과의 차이가 10^-3 이하인 값은 모두 정답으로 인정된다 했으므로 이렇게 제한해도 정답 처리를 받을 수 있다.

 

참고)

https://cplusplus.com/reference/ios/fixed/

https://cplusplus.com/reference/ios/fixed/