A: 1-4
D: 5-7
E: 8-9
가장 빨리 끝나는 A를 먼저 고르면 뒤에 남는 시간이 가장 길다.
exchange proof
현재 선택이 최적해를 망치지 않을 때만 그리디다
증명은 구호가 아니라, 임의의 최적해 첫 선택을 그리디 선택으로 바꿔도 남은 후보가 줄지 않는지 확인하는 절차다.
그리디 선택
교환
반례
회의 선택 교환 논증
B: 3-5
A: 1-4로 교환
A는 B보다 늦게 끝나지 않으므로, B 뒤에 가능했던 회의는 A 뒤에도 가능하다.
| 증거 | 통과 조건 | A가 아닌 신호 |
|---|---|---|
| 규칙 문장 | “가장 빨리 끝나는 회의”처럼 정렬 키가 한 문장이다. | 가장 짧은 회의, 가장 빨리 시작 등 후보 규칙을 구분하지 못함 |
| 교환 논증 | 최적해 첫 선택을 그리디 선택으로 바꿔도 남은 후보가 줄지 않는다. | 바꾸면 뒤의 선택 하나가 사라짐 |
| 반례 압박 | 동점, 겹침, 빈 입력, 하나 입력에서 규칙이 유지된다. | 작은 반례 하나라도 나오면 DP/탐색으로 전환 |
판정: “빠르다”가 그리디의 근거가 아니다. 현재 선택을 최적해와 교환할 수 있을 때만 A급 설명이다.