문제 태그

• 그리디
• 해시맵
• 정렬

한국어 문제 해석

수열 A가 주어진다. 정확히 K번 연산해야 한다.

한 번의 연산에서는 정수 하나를 골라, 그 값과 같은 원소를 전부 0으로 바꾼다.

모든 연산이 끝난 뒤 원소 합을 최소로 만들고 싶다.

문제 요약

• 같은 값은 한 번만 골라도 전부 사라진다.
• 어떤 값을 선택했을 때 줄어드는 총합은 그 값의 총 기여도와 같다.
• 총 기여도가 큰 값부터 K개 선택하는 것이 최적이다.

예시 워크스루

수열이 7, 2, 7, 2, 2, 9이고 연산 횟수가 2라고 하자.

• 값 7을 고르면 두 칸이 동시에 사라져 합이 14 줄어든다.
• 값 2를 고르면 세 칸이 동시에 사라져 합이 6 줄어든다.
• 값 9를 고르면 합이 9 줄어든다.

전체 합은 29다.

줄일 수 있는 양이 큰 순서대로 보면 14, 9, 6이므로 먼저 7과 9를 고르는 것이 최선이다.