문제/백준
백준 16562 친구비 [JAVA]
javaju
2021. 9. 21. 01:38
16562번: 친구비
첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (
www.acmicpc.net
풀이 방법
이 문제는 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하는 문제였습니다.
1) 친구가 아닌 경우 친구 사귀기
이때! 친구비가 더 적은걸로 친구비 변경해주기
2) M번의 친구 사귀기가 끝나면 한명씩 확인하면서 친구비 계산
3) 준석이가 가진 돈으로 친구를 다 사귈 수 있는지 확인
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_BJ_16562_친구비 {
static int N,M,K;
static int [] parents, friendFee;
static boolean [] check;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //학생수
M = Integer.parseInt(st.nextToken()); //친구관계수
K = Integer.parseInt(st.nextToken()); //가지고 있는 돈
friendFee = new int[N+1];
parents = new int[N+1];
check = new boolean[N+1];
for(int i=1;i<parents.length;i++) parents[i] = i;
st = new StringTokenizer(br.readLine());
for(int i=1;i<friendFee.length;i++) friendFee[i] = Integer.parseInt(st.nextToken());
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
union(a,b);
}
int friend=0, answer=0;
for(int i=1;i<parents.length;i++) {
int temp = find(i);
if(check[temp]) {
friend++;
continue;
}
if(K-friendFee[i]>=0) {
friend++;
answer+=friendFee[i];
K-=friendFee[i];
check[temp] = true;
}
}
System.out.println(friend==N?answer:"Oh no");
}
public static void union(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
if(aRoot<bRoot) parents[bRoot] = aRoot;
else parents[aRoot]= bRoot;
if(friendFee[aRoot]<friendFee[bRoot]) friendFee[bRoot] = friendFee[aRoot];
else friendFee[aRoot] = friendFee[bRoot];
}
public static int find(int x) {
if(parents[x]==x) return x;
return parents[x]=find(parents[x]);
}
}
|
cs |