[python/파이썬] 백준 1246 온라인 판매

[문제 출처]

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

1246번: 온라인 판매

 

[문제 풀이]

 

N개의 달걀이 있고, 잠재적 고객 M명이 있다. 잠재적 고객은 각각 p[i]보다 가격이 비싸면 계란을 구매하지 않는다.

따라서 달걀 가격은 p[i]와 같거나 작아야 한다.

고객에게 최대 1개의 달걀을 판매한다고 할 때, 수익이 최대가 되는 가격과 그때의 수익을 찾는 문제이다.

 

수익이 최대가 되게 하려면 최대한 비싸게 팔아야 하며, 그 가격은 고객이 정한 최대 가격과 일치한다.

하지만 여러 고객에게 판매하므로, 고객이 정한 최대 가격 중에 수익이 최대가 되는 가격을 골라야 한다.

 

또한 달걀의 개수는 고객보다 적을 수도 있고, 많을 수도 있다.

달걀의 개수가 더 적을 경우에는 무조건 전부 다 팔아야 한다.

하지만 달걀 개수가 더 많다면 최대가 되는 경우의 수를 찾아야 한다.

 

5개의 달걀이 있고, 4명의 잠재 고객이 있을 때,

각 고객의 최대 구매 가격은 

2 8 7 10 이다.

 

달걀이 5개이므로 모든 고객에게 팔 수는 있다. 하지만 모든 고객에게 판매하려면 가격은 최대 2여야 하며, 총수익은 8이 된다.

하지만 한 명의 고객을 포기하고 가격을 7로 한다면 21의 수익을 올릴 수 있다.

 

따라서 달걀의 개수가 고객의 수보다 더 많은 경우에는 모든 경우를 따져봐야 한다.

#1246

n,m = map(int, input().split())

p = []
for _ in range(m):
  p.append(int(input()))

p.sort() #오름차순으로 정렬

result = 0 #총 수익
A = 0 #달걀 가격
for i in range(m):
  #i번째 가격을 채택하면 p[i]보다 싼 가격을 원하는 고객은 구매하지 않으므로 구매할 고객의 수를 구한다.
  cnt = m-i 
  
  if n  <= cnt: #달걀의 수가 고객보다 적다면 모든 달걀을 다 팔아야 함
    sum = n * p[i]
  else:
    sum = cnt * p[i]
  
  if sum > result:
    result = sum
    A = p[i]

print("%d %d" %(A, result))