Greedy Florist

생각했던 것

내림차순으로 각 요소를 정렬해서 사람 수만큼 하나씩 쭉 빼주다가 마지막 사람에게 전부 몰아주는 방법을 생각했다. 하지만 예제를 보면서 틀렸다는 걸 알았다. 맨 마지막에 남은 값들을 다 몰아주면 결과값이 선형적으로 증가할 것이기 때문이다. 그래서 수정한 방법은 꽃의 개수를 균일하게 가져갈 수 있도록 분배하는 것이었다. 꽃의 가격에 영향을 주는 것은 이전, 이후의 꽃의 가격이 아닌 "해당 꽃을 사는 사람의 이전 구매 개수"이다. 따라서 개수를 잘 조절하면 최소값을 얻을 수 있다.

진행

해시맵에 사람 수만큼의 원소를 넣고 내림차순 정렬한 꽃 배열을 순회하면서 순차적으로 해시맵의 구매 개수를 늘려준다. 개수를 매번 더해주면서 꽃의 가격도 함께 계산해준다.

여담

역시나 정렬을 기본으로 생각하니 생각하기가 쉬웠다. 그리디 알고리즘이 워낙 직관적인 방법인 것도 있는 듯하다. 중간 난이도도 다른 주제보다 쉽게 느껴졌을 정도이니...