정렬 기준을 한 가지로 고정
종료 시각, 비용, 남은 용량처럼 선택 우선순위를 명확한 값으로 만듭니다.
그리디 규칙 검증 기준
그리디는 빠른 선택이 아니라 지금 선택해도 최적해를 잃지 않는다는 근거가 있을 때만 통과합니다.
현재 선택으로 바꿔도 손해 없음
최적해의 첫 선택을 그리디 선택으로 교체해도 답의 크기가 나빠지지 않는지 확인합니다.
작은 입력으로 규칙 반례 검토
가장 빠른 시작, 가장 짧은 길이, 큰 동전 우선 같은 직관 규칙은 반례부터 넣어 봅니다.
제출 전 남길 증거
회의실
끝나는 시간이 빠른 활동을 고르면 남은 선택 공간이 가장
넓습니다.
동전
임의 화폐 체계에서는 큰 동전 우선이 항상 최소 개수를 보장하지
않습니다.
제출 전
정렬 기준과 동률 처리까지 선택 규칙에 포함합니다.