알고리즘
[백준] 16562번 친구비 (Union-find) C++
1. 문제 이해준석이의 돈 : K원친구를 사귀려면 학생 i에게 A[i]만큼 돈을 주어야 한다.하지만 친구의 친구는 친구다!ex) 1의 친구가 5라면 1에게 또는 5에게만 돈을 주면 된다.-> 그렇다면 제일 비용이 적은 친구에게 돈을 주자그렇게 모든 사람과 가장 적은 비용으로 친구가 되는 방법을 구하라.2. 추상화5 3 2010 10 20 20 301 32 45 4Cost[]10원10원20원20원30원친구 구조 : 13 , 24 , 54 여기서 트리로 나타내야겠다 생각했다.3. 문제 설계모든 사람이 친구가 되려면 K(진석이가 가진 돈)원 내로 집합의 하나를 선택할수 있어야 한다.처음 생각으로는 백트래킹으로 1->3 3에서 더 없으면 cost[1], cost[3]비교 이렇게 생각했다.하지만 노드가 ..
