[Python] 1246번 온라인 판매

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

1246번: 온라인 판매

---

 

22/09/10

 

 

연습에서 풀었던 문제로, 문제 읽는 게 조금 시간이 걸렸던 문제이다.

 

이런 문제가 실전에서 나온다면 당황했을 것이다...

 

---

 

문제 접근 방식:

 

 

경래가 수익을 최대로 올리고 싶다고 했고, 한 고객에게 1개만 달걀을 팔기로 했다.

 

각 고객들이 제시한 최대 지불 금액 P가 리스트로 주어지고, 이 금액을 넘지 않는 선에서 고객들은 금액을 낼 수 있다고 했다.

 

또한, 달걀은 최대 M명까지만 살 수 있다고 했다. 고객들의 총명수는 N명이다.

 

위에까지 가 문제이다.

 

첫 번째로 주목한 점은 최대 수익이었다.

 

여기서 최대 수익을 올리려면, 나는 당연히 경래가 책정해야 할 가격이 각 고객들이 제시한 최대 지불 금액들 중에서 있어야 할 것이라고 생각했다.

 

왜냐하면, 최대 지불 금액이 아닌 금액이라면, 같은 달걀을 같은 사람에게 팔아도 수익이 최대 지불 금액일 때보다 항상 작기 때문이다.

 

예를 들자면, 모든 사람의 최대 지불 금액이 10이고 경래가 가격을 7로 책정했다면, 한 사람당 10씩이나 얻을 수 있는 걸 7밖에 못 얻는다.

 

두 번째로 주목한 점은 정렬의 여부였다.

 

만약 경래가 책정해야 할 가격을 고른다면 그 가격은 각 고객들이 제시한 최대 지불 금액들 중 하나에 존재하므로, 경래가 제시한 가격보다 작은 가격을 제시한 고객들은 전부 아웃된다.

 

이 사실 때문에 정렬을 해야 풀 수 있을 것이라고 유추를 했다. 만약 정렬을 해서 문제를 푼다면, 경래가 제시한 가격, 다시 말해 최대 지불 금액 중 하나를 고르고 이후 뒤에 있는 원소들은 이보다 작을 것이므로 무시하면 되는 것이다.

 

세 번째로 주목한 점은 최대 M명의 고객들에게만 달걀을 팔 수 있다는 점이었다.

 

만약 달걀이 고객보다 더 많다면, 다시 말해 M >= N이라면 그냥 정렬된 최대 지불 금액들의 리스트를 하나씩 돌면서 최대 수익이 나는지 확인하면 된다.

 

만약 고객이 달걀보다 더 많다면, 다시 말해 N > M이라면, 어차피 최대 M명의 고객들에게만 달걀을 팔 수 있으므로 최대 수익을 얻어 내려면 정렬된 최대 지불 금액들의 리스트를 M번까지만 돌면 된다.

 

마지막으로 주목한 점은 어떻게 정렬하는가? 였다.

 

내림차순이든 오름차순이든 상관없이 정렬한다면 한 고객의 최대 지불 금액을 고르면 그 고객의 인덱스를 기준으로 구매 가능인 고객들과 구매 불가능인 고객들로 나뉜다.

 

근데 나는 내림차순을 택했는데, 그 이유는 두 번째 주목할 점 때문이었다.

 

그 이후의 원소를 신경 쓰지 않는 방식을 택했기 때문에, 내림차순이 더 적합하다고 생각했다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1246번 온라인 판매
import sys
input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
P = sorted((int(input()) for _ in range(M)), reverse = True)
max_profit = 0
price = 0
for i in range(min(M, N)):
    profit = (i+1)*P[i]
    if profit >= max_profit:
        price = P[i]
        max_profit = profit
print(price, max_profit)