[백준 16112] 5차 전직

www.acmicpc.net/problem/16112

16112번: 5차 전직

그리디 문제

예시 두 세가지 정도 확인하면 식을 세울 수 있다. 주의해야할 건 롱롱으로 인한 오버 플로우 처리..

 

 

식 세우기

전체 n개의 퀘스트와 k개의 돌맹이를 활성화시킨다.

A1 A2 A3 .... AN

 

S1 S2 .. SK

S1이 활성화된 이후 쌓이는 경험치는 A2 + A3 + ... + An

S2에 쌓이는 경험치는 A3 + A4 + .. An

Sk에 쌓이는 경험치는 Ak+1 .. + An

일 것이다.

정리하면 (Ak+1 +  ... + An) * k개 이고 그 전엔 Aj * (j-1) 개가 될 것이다.

 

최대 경험치가 쌓여야 하므로 k개가 무조건 보장되는 An쪽에 큰 수가 있어야 한다. 따라서 오름차순 정렬한다.

#include <stdio.h>
#include <algorithm>

using namespace std;
int n, k;
long long arr[300001];
int main(void)
{
  scanf("%d%d", &n, &k);

  for (int i = 0; i < n; i++)
  {
    scanf("%lld", &arr[i]);
  }

  sort(arr, arr + n);
  long long sum = 0;
  for (int i = 1; i <= k; i++)
  {
    long long tmp = 1LL * arr[i] * i;
    sum += tmp;
  }

  for (int i = k + 1; i < n; i++)
  {
    long long tmp = 1LL * arr[i] * k;
    sum += tmp;
  }

  printf("%lld\n", sum);
  return 0;
}