[백준] 그리디 24855번: Natives

문제

Captain Cook and his team were captured by island natives. Not to be eaten, the adventurers must give some treasures to natives. It turned out that the captain has $n$ treasures.

Chieftain of the natives agrees to let the captain and his team go, if they give him at least half of his treasures. All treasures look pretty to him, so the chieftain agrees to get any treasures, he only wants to get at least half of them.

But actually each treasure has its own value known to Cook. The value of the $i$-th treasure is $a_i$. Help the captain to decide which treasures he should give to the chieftain so that the total value of the treasures he keeps to himself is maximum possible.

입력

The first line of input contains integer $n$ ($2 \le n \le 1000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 1000$).

출력

Output one integer --- the maximum possible total value of treasures that the captain can keep for himself after he gives at least half of his treasures to the natives.

Approach

사용 알고리즘: Greedy Algorithm

• 가장 싼 treasure들로 반을 채워서 줘버리면 된다
• 비싼 건 자기가 keep

1. 배열에 보물 n개 저장
2. 배열 sort
3. 보물 n/2의 갯수만큼 비싼 보물을 value에 업데이트

Source Code

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

int main() {
    
    // n입력받기 
    int n;
    cin >> n;
    
    // 보물 n개를 배열에 저장
    int treasures[n];
    for (int i = 0; i < n; i++)
    {
        cin >> treasures[i];
    }
    
    // sort the treasures 
    sort(treasures, treasures + n);
    
    
    int count = n / 2; // 줘야하는 보물의 수 
    int value = 0; // 캡틴이 keep할 수 있는 보물의 총 값을 저장하는 변수
    int index = n-1;
    while (count > 0) // 보물을 꼭 줘야할 만큼 줄 때까지
    {
        value += treasures[index]; // 가장 비싼 보물부터 내가 가짐
        
        index--;
        count--;
    }
    
    cout << value << endl; // 답안 출력

    return 0;
}