[Algorithm] [백준] 1246 - 온라인 판매 (그리디)

1. 최대 수익을 얻기
2. 달걀의 총 개수인 n개를 초과하여 팔 수는 없음
3. 각 고객들의 최대 가격을 p_list에 담는다.
4. 이를 오름차순 정렬한다. 그래야 첫번째 고객의 가격을 기준으로 할 때, 나머지 고객들은 당연히 첫번째 고객의 가격보다 크므로 기준을 잡을 수 있다.
5. for문을 돌면서 i를 기준으로, 현재 기준 고객을 포함한 나머지 고객까지의 고객의 수(m-i)가 달걀의 총 개수(n)보다 크면, 달걀을 초과하여 판매하는 것이므로 n을 곱한다.
6. 그렇지 않으면 (m-i)개를 판매할 수 있는 것이므로, (m-i)개를 곱한다.
7. max_total과 비교하여 최대 수익을 구하면 끝!

## 백준 1246 온라인 판매

import sys
input = sys.stdin.readline

n, m = map(int, input().split())  # n은 총 달걀 개수, m은 잠재적인 고객

p_list = []
for _ in range(m):
    p = int(input())  # 각 고객이 달걀 하나를 살 수 있는 최대 가격
    p_list.append(p)

p_list.sort()

a = 0  # 달걀을 책정한 가격 (최소)
max_total = -2147000000  # 최대 수익

for i in range(m):
    total = 0
    if m-i <= n:
        total = (m-i)*p_list[i]
    else:
        total = n*p_list[i]

    if total > max_total:
        a = p_list[i]
        max_total = total

print(a, max_total)