[백준] 20186 수 고르기 - C++

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

 

문제 설명

---

문제 풀이

 

#include<stdio.h>
#include<algorithm>
using namespace std;
int arr[5000];
int answer;
int main()
{
    int n, k, max = 0, tmp = 0;
    int i;

    scanf("%d%d", &n, &k);

    int cnt = n - 1;

    for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    sort(arr, arr + n);

    for(i = 0; i < k; i++)
        answer += (arr[cnt--] - i);

    printf("%d", answer);

    return 0;
}

문제 그대로 구현을 하려면 k만큼 중첩 반복문을 써야하기 때문에 구현 문제는 아니고, 빠르게 구할 수 있는 법을 생각했다.

정렬해서 큰 순서대로 누적만 하면 되기때문에 오름차순이든 내림차순이든 상관은 없을거라 생각해서 오름차순으로 정렬 후 역순으로 배열에 접근하는 방식으로 풀었다.