[백준 / BOJ] 16562 친구비

문제

출처 : www.acmicpc.net/problem/16562

16562번: 친구비

학생수N과 학생들의 친구관계수 M, 현재 가지고 있는 돈 K가 주어진다.

학생들과 친구를 하기위해선 일정한 금액을 내야한다.

준석이는 자신이 갖고있는 돈 K로 모든 학생과 친구를 할수없을수도있기때문에, 친구의 친구는 친구다 를 이용하기로했다. 이때, 준석이가 모든 학생과 친구를 하기위해 들어가는 최소비용을 출력하는 문제다.

모든 학생과 친구를 할수없으면 Oh no를 출력한다

 

풀이

학생들을 집합으로 묶고 해당 집합의 최솟값을 저장해주는 식으로 풀면 될것이라고 생각해서,유니온파인드를 사용해서 풀었다.

 

1. 친구관계수 M을 입력받을때, 학생들을 하나의 집합으로 합쳐준다.

 

2. 해당집합에서 최솟값을 뽑아 저장한다

 

3. 집합에 저장된값을 전부 더하고 해당값이 K보다 작거나 같다면 값을출력, 아니면 Oh no를 출력한다.

 

로직만 보면 상당히 간단한데, 반례찾는게 좀 힘들었다.

구현할때 주의할점이 유니온파인드를 한번 수행한다해서, 모든집합이 최소한의 연결관계로 연결되지 않을수도 있다는것이다.

예를들어, 학생 5,4,3,2 가 집합 2에 속한다고 가정하자.

그러면 포함관계는

5 -> 2

4 -> 2

3 -> 2

2 -> 2

이런식으로 되어야하는데,

5 -> 4 -> 2 

3 -> 2 

2 -> 2

이런식으로 만들어져 있을수도 있다는뜻이다.

 

5 3 10

1 1 1 1 1

5 4

5 3

5 2

답 : 2

을 입력해보자

 

따라서, 모든 포함관계를 만들어준후, 한번더 조상을 찾는 연산을 수행해, 자기자신의 최상단조상을 자기의 조상으로 합쳐줘야한다.

각 집합의 최소비용도 이 다음에 찾아줘야 하는것에 주의하자.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/16562%20%EC%B9%9C%EA%B5%AC%EB%B9%84/main.cpp

devxb/JJUNalgo