[백준 20186] 수 고르기

난이도

실버 III

📜문제

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

🌞풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b)
{
	return a > b;
}

int main()
{
	vector<int> v;

	int N = 0;
	int K = 0;

	cin >> N >> K;

	int value = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> value;
		v.push_back(value);
	}
	sort(v.begin(), v.end(), compare); // 내림 차순 정렬

	//빼지는 점수
	int minus = 0;
	for (int i = 0; i < K; i++)
	{
		minus += i;
	}

    //선택하는 전체 점수
	int total = 0;
	for (int i = 0; i < K; i++)
	{
		total += v[i];
	}

	int result = total - minus;

	cout << result << "\n";

	return 0;
}

• 빼지는 점수는 N개중 K개의 어떤값을 선택하던지 간에 정해져있다.

  • 선택한 값의 왼쪽 중에 선택 된 값의 개수만큼 빠지는 것이기 떄문에
  • ex) K = 3 이면 0 + 1 + 2 = 3 이고 K = 4 이면 0 + 1 + 2 + 3 = 6 이다.

• 그렇기 때문에 N개중 값이 제일 큰것을 K개 만큼 선택하는것이 점수의 최대값을 구할 수 있다.

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기