noeffserv   1년 전

시간과 조각의 이분매칭으로 코드를 짰습니다.

즉, 어떤 조각을 다운로드 할 수 있는 시간을 모두 구한 후


p[조각] = {가능한 시간의 집합};

위 처럼 조각의 인접리스트를 만들었습니다.


그래서 Matching 함수를 실행시켜 이분매칭을 진행했습니다.

그 후 답은 이분매칭 되지 않은 조각이 있을 경우 -1을 출력하고

모두 이분매칭 되었다면, 연결된 시간중 가장 큰 값을 답으로 출력했습니다.


왜 틀렸는지 모르겠네요. 도와주세요


hahaha   1년 전

음... 이 문제가 단순히 이분매칭이 아니라

파일을 모두 다운받을 수 있는 최소 시간을 구해야 하는데.. 위 소스상에서

가장 빠른 시간에 파일이 다운받을 수 있도록 처리하는 부분이 없는것같아요 ㅠ

제 풀이도 시각과 조각의 이분매칭이긴 한데, 시각을 왼쪽 그룹, 조각을 오른쪽 그룹으로 해서

매 초마다 그 시각에 가능한 조각을 매칭하게 하고 매칭의 수가 n이 되면 그때 매칭을 중지하도록 했어요

아마 조각에 시각을 매칭시키면 각 조각이 다운받아질 시각을 찾는 과정에서 초반 조각들까지에서의 최대 매칭을 그리디하게 찾다가

늦은 시각을 택해버릴 여지가 있어서 예외가 생기는 듯 합니다

noeffserv   1년 전

음... 시간의 집합이 오름차순 정렬이 되어 있어서 그리디하게 접근 해도 된다고 저는 생각했었는데.. 음 두분 조언 바탕으로 다시 생각해볼게요 답변 감사드립니다.

noeffserv   1년 전

두 분 말씀하신게 맞네요


p[조각] = {가능한 시간의 집합};

에서

p[시간] = {가능한 조각의 집합}; 로 고쳐서


어셉받았습니다. 감사합니다.

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