unilep   1년 전

선을 연결하는 가격들의 리스트 중 비싼거 k개는 안내도 되기때문에
정렬을 해야할 필요가 있을거 같았고...

그 가격들의 리스트 valList 를 정렬하기위해
벡터 tmp를 따로 받아서 tmp를 정렬했습니다.
valList를 정렬하면 나중에 pop할때 문제가 생길거같아서요

그런데 시간초과가 나는것을 보니 방법이 틀린거같은데

힌트좀 주실수있나요?

lyzqm   1년 전

완전탐색으로는 시간초과가 날겁니다.

다익스트라 알고리즘을 변형해서 해결할 수 있습니다

chogahui05   1년 전

코레스코에서는 K개의 선에 대해서는 공짜로 연결해 주기로 했고

나머지 컴에 대해서는 연결 되어있거나 안 되어 있어도 된다.

이 때 남은 것 중 가장 비싼 가격을 x라고 합시다.


만약에 x일 때 연결이 안 되었는데 x-1일 때 연결이 될 수 있을까요?

그리고 K개의 선에 대해서 공짜로 연결을 해 주는 경우에 x를 초과하는 선에 대해서 공짜로 까는 게 이득일까요?

아니면 그렇지 않은 선에 대해서도 공짜로 까는 게 이득일까요?


이 두 힌트를 잘 조합해 보세요.

이 정도면 거의 답을 대놓고 알려드린 수준인데.. 잘 생각해 보세요.

chogahui05   1년 전

그런데 백조의 호수는 푸신 거 같으시니까..

이 문제도 아주 조금만 생각해 보시면 충분히 푸실 수 있을 거 같아요.

댓글을 작성하려면 로그인해야 합니다.