문제 링크 : 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
1. 접근 방법
union-find로 친구들을 묶으면 된다고 생각했고, 나름 쉽게 잘 풀렸던 것 같다
2. 풀이 코드
🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/16000/16562.py
GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장소입니다.
BOJ를 Python으로 해결한 코드의 저장소입니다. Contribute to mintropy/baekjoon_py development by creating an account on GitHub.
github.com
📕코드 해설
각 친구 쌍을 받으며 union 과정을 진행하고, 모든 친구 쌍을 한번 더 돌면서 최소 친구 비를 확인한다.
처음 몇 차례 틀렸던 부분중 하나가 친구 쌍에서 가장 낮은 친구 비를 찾는 과정이고, 이를 해결하기 위해 모든 친구를 한 번 더 확인하며 union 된 모든 친구들 중 가장 낮은 친구 비를 구한다
3. 생각 정리
프로젝트를 진행하며 적용했던 type hint, docstring을 조금씩 추가하는 방식으로 작성해보았다. 더 늘려가며 적용해봐야겠다고 생각이 든다
'CS > 알고리즘 & 문제풀이' 카테고리의 다른 글
| [Python] 백준 13164 행복 유치원 (0) | 2022.02.27 |
|---|---|
| [Python] 백준 21924 도시 건설 (0) | 2022.02.21 |
| [Python] 백준 18809 Gaaaaaaaaaarden (0) | 2022.02.02 |
| [Python] 백준 2173 양파깡 만들기 (0) | 2022.01.13 |
| [Python] 백준 2671 잠수함식별 (0) | 2021.12.17 |