[2020 Goricon] BOJ 20117 호반우 상인의 이상한 품질 계산법

문제 링크 : www.acmicpc.net/problem/20117

20117번: 호반우 상인의 이상한 품질 계산법

그리디 알고리즘으로 해결할 수 있는 문제이다.

판매하는 물건들을 가장 비싸게 팔 수 있는 가장 좋은 방법은 가장 싼 물건과, 가장 비싼 물건을 묶어 파는 것이다.

문제에서 물건의 묶음이 짝수인 경우, 가격의 중앙값은 (묶음 개수/2+1)번째 호반우로 정의했기 때문에

(k1, k2) 묶음에 대해서 반드시 k2의 가격이 중앙값이 된다. 따라서, (2, 9)의 형태로 묶으면 이 묶음을 9 * 2 = 18원에 팔 수 있게 된다.

 

따라서 각 호반우들을 가격 순으로 정렬한 후, 왼쪽 끝과 오른쪽 끝에 포인터를 두어 문제를 해결한다.

왼쪽 포인터가 가리키는 물건 하나와 오른쪽 포인터가 가리키는 물건 하나를 묶어, 더 비싼 가격 * 2에 파는 과정을 반복한다. 이 과정을 반복하다 보면 마지막에 남는 호반우는 하나이거나 없을 것이다.

마지막에 남은 호반우는 원래 가격에 팔면 된다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
typedef pair<int, int> p;
 
int n, answer;
int highest, lowest;
int qcnt[1001];
vector<int> qual;
 
void init() {
    int input;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> input;
        if (qcnt[input] == 0) qual.push_back(input);
        qcnt[input]++;
    }
 
    sort(qual.begin(), qual.end());
 
    lowest = 0;
    highest = qual.size() - 1;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
 
    while (1) {
        if (lowest > highest) break;
        int low_cnt = qcnt[qual[lowest]];
        int high_cnt = qcnt[qual[highest]];
        if (lowest == highest) {
            answer += qual[highest] * high_cnt;
            qcnt[highest] = 0;
            lowest++;
            continue;
        }
        if (low_cnt < high_cnt) {
            answer += qual[highest] * low_cnt * 2;
            qcnt[qual[highest]] -= low_cnt;
            qcnt[qual[lowest]] = 0;
            lowest++;
        }
        else {
            answer += qual[highest] * high_cnt * 2;
            qcnt[qual[lowest]] -= high_cnt;
            qcnt[qual[highest]] = 0;
            highest--;
        }
    }
 
    printf("%d\n", answer);
 
    return 0;
}