최솟값부터 선택해 얻은 초콜릿 배열을 A라 하고, 최적해 B는 A가 아니라 가정합시다.
B의 크기는 A 이상입니다.
A와 B 속 원소를 크기 순으로 정렬하면 A의 원소는 필연적으로 B의 원소보다 작거나 같습니다.
A와 B의 원소를 순서대로 짝을 지은 후, 짝이 안 맞는 원소를 A에 넣으면 새로 만들어진 A`은 B와 개수가 같으면서도 초콜릿에 지불하는 값이 더 적은 배열입니다.
이는 B가 최적해라는 가정에 모순이므로, 최적해 B는 A입니다.
맞는 증명인지는 모르겠네요.

ksc919 4년 전
https://codeforces.com/contest...
지난 질문들과 비슷하게...
현재 그리디란 개념이 어떤건지 대충이나마 알고 있는 수준입니다...(강의를 들으며 공부하고 있고, 아직 코드구현력수업을 듣고 있습니다)
위 문제에서 그리디 알고리즘을 적용시킬 때, 반드시 최적해가 나온다는 증명을 어떻게 해야하나요???
제가 아는거라고는 귀납법,연역법 정도밖에 없는데...
항상 최소값을 선택하면 반드시 답이 나오기에, 오름차순 정렬이 필요하다 라고 생각했습니다..
근데 이걸 증명을 못하겠습니다... 계속 감으로만 풀고 있는거라고 생각됩니다.
조언 좀 부탁드립니다.