[BOJ 28360] 양동이 게임

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

28360번: 양동이 게임

 

- 문제 요약

 

찬우는 천하제일 코딩대회 참가자들과 간단한 게임을 하기로 했다.

게임은 '양동이 게임'으로, 맨 위의 양동이에 물을 100만큼 부어 흘려보냈을 때 최종적으로 가장 많은 물이 담긴 양동이를 선택하면 이기는 게임이다.

양동이를 고르기 전까지는 연결 상태를 알 수 없다.

하지만 찬우는 양동이들이 어떻게 연결되어 있는지 이미 알고 있는 상태였다!

찬우가 게임을 이기기 위해서 골라야 하는 양동이에는 얼마만큼의 물이 들어있는지 알아보자.

(연결하는 양동이가 같은 호스가 여러 개 주어지지 않는다.)

 1번 양동이가 항상 맨 위에 있으며, 1의 양만큼 물이 채워져 있는 양동이에 K>0개의 나가는 방향 호스가 연결되어 있으면 양동이가 비워질 때까지 호스당 1/K씩 흐른다.

또한 양동이의 번호가 더 작을수록 위에 있기 때문에, 물은 항상 번호가 작은 양동이에서 큰 양동이로 흐른다.

 

 

- 알고리즘 정리

 

물은 항상 작은 번호에서 큰 번호의 양동이로 흐르고, i-1번 양동이에서 물이 없어지면 i번째 양동이에는 더이상 물이 차지 않습니다.

그러므로 1번 양동이부터 번호순으로 물을 흘려주는 과정을 구현하면 됩니다.

나가는 방향으로 연결된 호스가 없는 양동이 속 물의 최대값이 정답입니다. 

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 51
int n,m;
double arr[MAX];
vector<int>v[MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	arr[1]=100;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s,e;
		cin>>s>>e;
		v[s].push_back(e);
	}
	for(int i=1;i<=n;i++){
		if(v[i].empty()){
			continue;
		}
		double w=arr[i]/v[i].size();
		for(auto j:v[i]){
			arr[j]+=w;
		}
		arr[i]=0;
	}
	cout<<fixed<<setprecision(20);
	cout<<*max_element(arr+1,arr+n+1);
}

코드 제출 결과