그리디 알고리즘의 유명한 문제이다. 그리디 알고리즘은 그의 정당성을 증명하는 것이 까다로운 것 같다. 이건 워낙 잘 알려져 있어서 그냥 풀었지만 증명하는 법은 알아두는 것이 좋을 듯 하다.그리디 알고리즘이 최적해를 구한다는 것에 대한 증명탐욕적 선택 속성(Greedy choice property)탐욕적 선택은 항상 안전하다는 것을 보여야 한다. 즉, 탐욕적 선택으로 전체 문제의 최적해를 반드시 구할 수 있다는 것을 보여야 한다.보통 탐욕적 선택을 포함하지 않는 최적해의 존재를 가정하고, 이것을 적절히 조작하여 탐욕적 선택을 포함하는 최적해를 만들어 내는 과정으로 증명하곤 한다.최적 부분 구조[전체 문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해] 임을 증명해야 한다. 탐욕적 선택 속성전체 회의의 ..