티스토리 뷰
https://www.acmicpc.net/problem/16562
16562번: 친구비
첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (
www.acmicpc.net
새로 이사 온 곳에 친구가 없어서 풀어 본 문제입니다 ㅠㅠㅠ
문제는 간단합니다. 친구의 친구도 친구로 치는데 이 때 무리들에게 최소 얼마를 줘야 모두 친구가 될 수 있는 지 문제입니다.
먼저 친구 그래프를 만든 뒤, dfs 로 해당 그래프에서 가장 작은 친구비를 요구하는 친구들만 골라 합을 구하면 됩니다. 만약 k보다 합이 크면 Oh no 입니다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 1328 고층빌딩 C++ (0) | 2022.02.10 |
|---|---|
| 백준 1765 닭싸움 팀 정하기 C++ (0) | 2022.02.07 |
| 백준 11402 이항계수 4 C++ (0) | 2022.01.15 |
| 백준 2150 Strongly Connected Component C++ (0) | 2022.01.09 |
| 백준 9576 책 나눠주기 C++ (0) | 2021.12.20 |
댓글