2463

알고리즘/acmicpc 2015. 9. 29. 14:05 Posted by 아는 개발자

내가 직접 푼 문제는 아니고 게시판의 글을 참조해서 풀었는데 정말 감탄할만한 방법으로 풀었다... 기본적으로 이 문제는 MST의 형태를 가진 문제이다. 여기서 MST는 최소 스패닝 트리가 아니라 최대 스패닝 트리이다.


문제가 요구하는 조건이 다르다보니 기존 방식으로 트리를 형성해야 문제를 풀 수 있다.


문제를 푸는 핵심은 각각의 클라우드 사이를 연결 시키기 전에 형성된 에지들을 제외하고는 모든 에지들의 가중치를 더해야 한다는 점.


기존에 형성된 에지들의 가중치를 pastCost에 넣어서 정리하는 깔끔함이 놀라웠다...


게다가 이미 두 클라우드의 크기가 2 이상인 경우는 두 클라우드의 크기를 곱해서 가중치를 정리하는 방식까지. 이해하는 것은 별로 어려운 것은 아니나 이렇게 생각해낸다는 것 자체가 어려운것 같다.


이것을 어떻게 생각해냈는지 참으로 감격스럽다..


나는 언제쯤 이런 경지에 오를 수 있을지....



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2437  (0) 2015.10.09
2616  (0) 2015.10.03
2463  (0) 2015.09.29
9079  (0) 2015.09.13
2465  (0) 2015.09.08
2457  (0) 2015.09.04