문제
https://www.acmicpc.net/problem/16112
문제해설
너무 길어 링크 참조
문제풀이
가장 많이 경험치를 모으려면
첫번째 고르는 퀘스트는 버리기 때문에 오름차순으로 정렬하여
k개 만큼 큰수부터 더해주면 된다.
이중 반복문으로 해결하면 좋겠지만 그러면 시간초과가 발생한다.
그렇기 때문에 반복문을 한번 돌면서
미리 k개 만큼을 곱하면서 더해주었다.
그리고 결과가 int를 벗어날 수 있기 때문에 long long을 사용해야 한다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll n, k; cin >> n >> k;
vector<ll>arr(n);
for (int i = 0; i < n; i++)
cin >> arr[i];
ll sum = 0;
sort(arr.begin(), arr.end(), less<ll>());
for (ll i = 1; i < n; i++) {
ll tmp = arr[i] * min(i, k);
sum += tmp;
}
cout << sum;
return 0;
}