혹시 다른 분께 도움이 될까봐 셀프 댓글 남깁니다....
둘째 줄부터 N+1번째 줄에 걸쳐 주어지는 각 아파트 단지의 위치와 이 아파트 단지에 사는 학생의 수는 아파트 단지의 위치값을 기준으로 오름차순으로 주어지지 않습니다.
아파트 단지의 위치값을 기준으로 오름차순으로 정렬한 뒤에 문제 푸셔야 합니다.
2513번 - 통학버스
혹시 다른 분께 도움이 될까봐 셀프 댓글 남깁니다....
둘째 줄부터 N+1번째 줄에 걸쳐 주어지는 각 아파트 단지의 위치와 이 아파트 단지에 사는 학생의 수는 아파트 단지의 위치값을 기준으로 오름차순으로 주어지지 않습니다.
아파트 단지의 위치값을 기준으로 오름차순으로 정렬한 뒤에 문제 푸셔야 합니다.
댓글을 작성하려면 로그인해야 합니다.
puberty4ever 4년 전
그리디 알고리즘의 탐욕적 선택 속성을 어떻게 증명해야 될 지 잘 모르겠습니다ㅜㅜ
손으로 직접 예제를 풀어보면서 학교에서 가장 멀리 있는 아파트 단지의 학생들부터 태워서 오는게 최선의 방법이라는 건 알아냈습니다.
근데 그 방법으로 구한 정답이 최적의 해들 중에 하나라는 그 정당성을 어떻게 입증해야 할 지 감이 오지 않습니다.
간단하게 라도 어떻게 증명할 수 있을 지 알려주신다면 감사하겠습니다!