백준 20117 호반우 상인의 이상한 품질 계산법(C++)

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

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

using namespace std;

vector<int> arr;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int ans = 0;
    cin >> n;

    arr.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sort(arr.begin(), arr.end());


    for (int i = n - 1; i > n / 2; i--) {
        ans += arr[i] * 2;
    }

    if (n % 2 == 1) {
        ans += arr[n / 2];

    } else {
        ans += arr[n / 2] * 2;

    }


    cout << ans;

    return 0;
}

1. 문제

n개의 호반우의 품질이 주어진다. 호반우는 낱개로 팔 경우 품질의 가격으로 팔리게 된다. 그러나 묶음으로 팔 때는 모든 호반우의 가격을 묶음의 중앙값으로 정의한다. 묶음이 짝수인 경우 (묶음개수/2+1)번째 호반우가 중앙값이 되고, 홀수인 경우 ((묶음개수+1)/2)번째 호반우가 중앙값이 된다.

 호반우를 적절히 묶어 최대 이윤을 내려고 할 때, 그 이윤을 구하라.

2. 풀이

우선 예제의 결과가 어떤 방법으로 나왔는지 생각해보자. 다음의 예제가 주어진다.

4
4 2 8 9

이를 다음과 같이 묶는다.

위 경우를 보면 가장 큰 수와 가장 작은 수를 묶으면 중앙값의 정의에 따라 (2/2+1)번째, 즉 큰 수가 중앙값이 된다. 이를 이용하여 최대 이윤을 뽑아낼 수 있다.

    sort(arr.begin(), arr.end());

우선 가장 큰 값을 중앙값으로 뽑기 위해 정렬한다.

    for (int i = n - 1; i > n / 2; i--) {
        ans += arr[i] * 2;
    }

    if (n % 2 == 1) {
        ans += arr[n / 2];

    } else {
        ans += arr[n / 2] * 2;

    }

정렬한 결과를 뒤에서부터 가운데로 올 때 까지 연산한다. 가장 큰 수와 가장 작은 수를 묶으면 중앙값인 큰 수로 작은 수가 바뀌므로 큰 수*2로 이윤을 계산할 수 있다.

 그 후 n이 홀수면 중간에 하나의 값만 남게 되므로 arr[n/2]를 더하고, 짝수면 위와 같은 상황이므로 arr[n/2]*2를 더한다. 결과를 출력하면 정답을 구할 수 있다.