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

문제

경래는 닭을 기르는데 올 겨울 달걀 풍년으로 함박 웃음을 짓고 있다. 그리고 이 달걀을 영양란으로 둔갑하여 옥션에 판매하려한다.

경래는 총 N개의 달걀이 있고, 그의 잠재적인 고객은 총 M명이다. 그리고 각각의 i번째 고객은 각자 달걀 하나를 Pi 가격 이하로 살 수 있다고 밝혔다.

경래는 영양란이라 속인 죄책감에 한 고객에게 두 개 이상의 달걀은 팔지 않기로 하였다. 하지만 위의 규칙 하에 수익은 최대로 올리고 싶기에 얼마로 팔지 고민하고 있다. 즉, A가격에 달걀을 판다고 하면 Pi가 A가격보다 크거나 같은 모든 고객은 달걀을 산다는 뜻이다. (물론 달걀 총 수량을 초과하여 팔 수 는 없다)

문제는 이러한 경래를 도와 최대 수익을 올릴 수 있는 달걀의 가장 낮은 가격을 책정하는 것이다.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 입력된다. 둘째 줄부터 M+1번째 줄까지 i+1번째 줄에는 Pi(1 ≤ Pi ≤ 1,000,000)가 입력된다.

출력

첫째 줄에 경래가 책정한 가격과 이 가격으로 올릴 수 있는 수익을 출력한다.

예제 입출력

• 예제 입력 1

5 4
2
8
10
7

• 예제 출력 1

7 21

Solution

이거 완전 양아치잖아...

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int> vec(M+1);
    for(int i = 1; i <= M; i++) cin >> vec[i];
    sort(vec.begin(), vec.end());
    long long sum = 0;
    int value = 0;
    for(int i = 1; i <= M; i++){
        if(sum < vec[i] * (M - i + 1) && ((M - i + 1) <= N)){ 
            value = vec[i];
            sum = value * (M - i + 1);
        }
    }
    cout << value << " " << sum << '\n';
}

일단 P의 데이터를 정렬한다. 그리고 P[i] 에 들어올 수 있는 최대 데이터가 1,000,000이고 M의 최대값이 1000이므로 최대 값을 계산하는 변수는 long long으로 선언해 둬야 한다. (Overflow 문제)

가장 작은 값부터 일단 계산해본다. 한 사람당 2개 이상 구매 불가이므로 한 사람당 1개만 산다고 생각해본다.

작은 값을 부른 사람은 자기를 포함해서 나머지 자기보다 큰 값을 부른 사람들이 모두 살 수 있다는 걸 알 수 있다. 고로 for문을 돌리며 해당 경우에 M - i + 1 명이 해당 가격으로 계란을 산다고 생각 해 보는 것이다.

그 중에서 최댓값을 찾으면 되는 간단한 문제.