백준 1246번 파이썬 문제풀이 : 온라인 판매

문제 링크 : https://www.acmicpc.net/problem/1246

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)가 입력된다.

출력

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

 

 

# 문제풀이 ( 알고리즘 분류 : 정렬 )

예제를 살펴보면 달걀의 갯수는 5개 이지만 구매자는 4명이기 때문에 실제 판매할 수 있는 달걀의 갯수는 4개이다.

2 * 4 = 8, 7 * 3 = 21, 8 * 2 = 16, 10 * 1 = 10 중에서 가장 수익을 많이 낼 수 있는 경우의 수는 7원으로 3개를 파는 것이다.

 

위 규칙에서 입력받은 가격들을 sort 하고 reverse 하여 정렬한 후 index + 1을 가격과 곱해주면 해당 경우의 가격이 나오게 된다. 

 

ex) 10, 8, 7, 2 ( 정렬 후 ) 10에 대한 인덱스는 0 임으로 0 + 1 * 10 인 10 이 최종 결과가 되며 7은 인덱스 2 임으로 

2 + 1 * 7 하여 21이 최종 결과가 된다. 

 

n, m = map(int, input().split())
p = []
for _ in range(m):
    p.append(int(input()))
p.sort(reverse=True)
max_money = 0
max_cost = 0

입력받은 인원수 m만큼 p 배열에 입력받음과 동시에 append하여 추가해준다.

p.sort(reverse=True) 하여 배열을 정렬하고 역순으로 재정렬 해준다.

max _ money = 판매 총 금액

max _ cost = 판매 액 ( 달걀 1개 )

 

for idx, i in enumerate(p):
    if idx + 1 <= n:
        if (idx + 1) * i > max_money:
            max_money = (idx + 1) * i
            max_cost = i
    else:
        break
print(max_cost, max_money)

enumerate 를 사용하여 해당 값의 index와 함께 반복문을 사용한다. 

max_money 와 max_cost 값을 선언하여 계산한 값이 더 크다면 변수에 대입하면 된다.

여기서 중요한 점은 가격을 입력한 인원이 4명이기 때문에 for 문만 사용하게 된다면 4명에게 전부다 파는 경우의 수까지 계산하게 된다.

하지만 달걀의 갯수가 3개가 된다면 4명에게 다 팔지 못하기 때문에 idx (인덱스) + 1이 n보다 작거나 같을 때만 비교해줘야 한다.