[C++] 백준 1246 : 온라인 판매

#include <iostream>
#include <algorithm>

using namespace std;

int main(void){
    int N, M, max = 0, idx;
    scanf("%d %d", &N, &M);
    int * arr = new int[M];

    for(int i=0; i<M; i++){
        scanf("%d", &arr[i]);
    }

    sort(arr, arr + M, greater<int>()); // 내림차순 정렬 (큰수 ~ 작은수)

    for(int i=0; i<M; i++){
        if(i < N){ // 1명 당 1개씩, N개 이상의 달걀은 팔 수 없음
            if(arr[i] * (i+1) > max){ // 인덱스 크기만큼의 사람이 달갈을 살 수 있음 (역순)
                max = arr[i] * (i+1);
                idx = i;
            }
        } else {
            break;
        }
    }

    printf("%d %d", arr[idx], max);

    return 0;
}

오늘의 키포인트

  • c++ 내림차순 정렬법 :
sort(arr, arr + N, greater<int>());
  • 1인당 1 달걀이기에 내림차순으로 정렬하고 인덱스(사람 수) * 인덱스 값(달걀 값) 을 구하면 된다. 인덱스가 곧 사람 수 이기때문에, 인덱스가 N 을 넘지 않게 한다면 달걀 전체의 개수를 제한할 수 있다.

좋은 웹페이지 즐겨찾기