백준 16112 5차 전직(그리디)

https://www.acmicpc.net/problem/16112

16112번: 5차 전직

익숙한 메이플 얘기가 나와서 반가웠당

아케인스톤 활성화 시키고 경험치 많이 먹으려고 하는거 같은데 여러개 활성화가 가능하다고 한다(k개 만큼)

가장 경험치를 많이 먹기 위해선 제일 경험치통이 작은 아케인스톤부터 하나씩 활성화 해야한다

 

3 2
100 300 200

100 활성 (200 + 300)

200 활성 (300)

4 2 
100 300 200 400

100 활성 (200 + 300 + 400)

200 활성 (300 + 400)

 

살짝 규칙이 보이는데 오름차순으로 sort()를 시켜주고

exp[i] * use_cnt를 계속 더해주면된다.

 

여기서 중요한 point는

if use_cnt < k일 때 use_cnt++ 인 것

why?

=> 아케인스톤을 활성화시킨 다음에 자신을 제외한 나머지를 먹어야하는데 k개까지 활성화 시킬 수 있기 때문에

use_cnt가 k보다 작으면 1개씩 활성화 시켜줘서 수를 늘려야함

n,k = list(map(int,input().split()))
exp = list(map(int,input().split()))
exp.sort()

res = 0
use_cnt = 0
for i in range(n):
    res += use_cnt * exp[i]
    if use_cnt < k:
        use_cnt += 1
print(res)