puberty4ever   4년 전


그리디 알고리즘의 탐욕적 선택 속성을 어떻게 증명해야 될 지 잘 모르겠습니다ㅜㅜ

손으로 직접 예제를 풀어보면서 학교에서 가장 멀리 있는 아파트 단지의 학생들부터 태워서 오는게 최선의 방법이라는 건 알아냈습니다.

근데 그 방법으로 구한 정답이 최적의 해들 중에 하나라는 그 정당성을 어떻게 입증해야 할 지 감이 오지 않습니다.

간단하게 라도 어떻게 증명할 수 있을 지 알려주신다면 감사하겠습니다!

puberty4ever   3년 전

혹시 다른 분께 도움이 될까봐 셀프 댓글 남깁니다....

둘째 줄부터 N+1번째 줄에 걸쳐 주어지는 각 아파트 단지의 위치와 이 아파트 단지에 사는 학생의 수는 아파트 단지의 위치값을 기준으로 오름차순으로 주어지지 않습니다.

아파트 단지의 위치값을 기준으로 오름차순으로 정렬한 뒤에 문제 푸셔야 합니다.

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