[백준 17073번] 나무 위의 빗물 (C++)

문제링크 : https://www.acmicpc.net/problem/17073

17073번: 나무 위의 빗물

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, W;
double cnt;
int arr[500001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> W;
    for(int i=0; i<N-1; i++)
    {
        int u, v;
        cin >> u >> v;
        arr[u]++;
        arr[v]++;
    }

    for(int i=2; i<=N; i++) //1은 루트이므로 2부터
    {
        if(arr[i]==1) cnt++; //리프노드 카운트
    }

    cout.precision(11); //소수점 자리 고정
    cout << W / cnt;
    
}

 

물이 움직이지 않는 상태는 현재 노드가 리프노드인 상태를 말한다. 

그리고 Pi가 0보다 큰 정점들 또한 마찬가지로 리프노드를 말한다.

부모 노드 및 조상 노드들의 경우 자식이 존재하여 밑으로 물이 빠지기에 값이 0일 수 밖에 없다.

따라서 총 물의 양 W에 리프노드의 갯수를 나눈 것이 정답이 된다.

 

해당 문제에서 정답과의 차이가 10 ^ -3 이하인 값은 모두 정답이라고 했으므로 단순히 나누기만 하는 것이 아니라 출력할 때 소수점 자리에 신경을 써줘야한다.

위 코드에서는 예제와 똑같은 값을 출력하기 위해 소수점을 저렇게 줬지만, 오차범위 이내이기만 하면 되므로 적절히 조절해서 출력해주면 된다.