[백준 20186번] 수 고르기 (C++)

문제링크 : https://www.acmicpc.net/problem/20186

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;    

    vector<int>v;

    for(int i=0; i<N; i++)
    {
        int n;
        cin >> n;
        v.push_back(n);
    }

    sort(v.rbegin(), v.rend());

    int result = 0;
    for(int i=0; i<K; i++)
    {
        result += (v[i]-i);
    }
    cout << result;
    return 0;
}

 

규칙에 따른 최대 점수를 내기 위해서는 자신의 점수와 선택된 수의 개수 차이가 가장 커야 한다.

선택된 수의 개수는 0부터 시작해 하나씩 증가하기에, 이에 맞춰 점수를 내림차순 정렬해 가장 큰 점수랑 매치되도록 한다.

이를 K만큼 반복해서 구한 값을 더해주면 된다.