백준 16562번
-
(백준 16562번 친구비 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) Union Find 3PROGRAMMING/C++ 2024. 5. 9. 21:23
백준 16562번https://www.acmicpc.net/problem/16562 유니온 파인드 문제인 걸 알고봐서 아이디어를 내는 건 어렵지 않았다.연결된 그래프 중 가장 친구비가 작은 노드를 root node로 지정하고, root node들을 다 더한 값이 이준석 학생이 가진 돈보다 많으면 된다도 생각했다. 고런데,,,!! 29%에서 안되는 것이 아닌가! 그래서 찾은 문제점 1. 일단 반례부터 투척(출처) : https://www.acmicpc.net/board/view/81875반례 :5 3 2010 20 20 10 301 32 45 4답 : 20 node의 번호와 node의 value는 다르다. 1번이라고 해서 무조건 작은 친구비를 갖는게 아님!!!! 위 반례를 통해 그 부분을 수정할 수 있..