백준 20186번 : 수 고르기

• 문제 선정 이유 : 알고리즘 문제 해결 재활 용 낮은 난이도 문제 풀이
• Solved.ac 기준 실버 4
• 사용언어 C++

문제 해석

1. N개의 숫자 모음에서 K개의 숫자를 선택
2. 각 숫자를 i, i', i'', ..., 라고 할 때 점수는 i + (i'-1) + (i'' - 2) + ... + (i''' - (K-1))

문제 풀이

1. 결론적으로 답은 K개 숫자의 최댓값을 구한 뒤 1~(K-1)까지의 합을 빼는 것
2. 입력 받은 값을 내림차순하여 K개수만큼 더해주고 1~(K-1)까지의 합을 빼면 답 도출 가능

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, k;										// 입력 받을 N, K

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;

	vector<int> arr(n);							// 배열을 입력 받을 Vector

	for (int i = 0; i < arr.size(); i++) {		// 배열 입력
		cin >> arr[i];
	}

	sort(arr.rbegin(), arr.rend());				// 내림차순 정렬

	int ans = 0;

	for (int i = 0; i < k; i++) {
		ans += arr[i] - i;						// arr[i](입력 받은 수 중 큰 수) - i(왼쪽에 값이 있는 개수)
	}
	
	cout << ans;

	return 0;
}