2018. 11. 20. 00:03, 알고리즘/BOJ
https://www.acmicpc.net/problem/2084
그럭저럭 유명한 Greedy입니다. 우선 degree의 합이 홀수면 불가능하고, 이후엔 간선이 가장 많이 남은 것들을 계속 연결해주면 됩니다. 이것이 성립함을 보이려면 a-b / c-d라는 edge를 a-c / b-d로 바꾸어도 문제가 없다는 점을 가지고 어찌저찌 하면 됩니다.
'알고리즘 > BOJ' 카테고리의 다른 글
| [BOJ] 15481번: 그래프와 MST (0) | 2018.11.21 |
|---|---|
| [BOJ] 8452번: 그래프와 쿼리 (2) | 2018.11.20 |
| [BOJ] 13560번: Football (0) | 2018.11.20 |
| [BOJ] 1941번: 소문난 칠공주 (0) | 2018.11.19 |
| [BOJ] 2553번: 마지막 팩토리얼 수 (2) | 2018.11.18 |
| [BOJ] 15329번: Secret of Chocolate Poles (0) | 2018.11.14 |
Comments