[백준] 1246 - 온라인 판매 (Python)

문제 링크

알고리즘

• 정렬

주의할 점

• 최대 수익을 올릴 수 있는 달걀의 가장 낮은 가격을 책정해야 한다.
• 한 고객에게 하나의 달걀만 팔 수 있다.

풀이

고객이 제시한 금액은 달걀이 그 가격 이하라면 사겠다는 뜻이다. 따라서 만약 고객들이 [5, 7] 의 금액을 제시했다면 6은 검사하지 않아도 된다. (어차피 7로 해도 사기 때문에)

이중반복문으로 문제를 해결했다.
시간복잡도는 O(n2)
고객 수가 최대 1000명이고 시간제한은 2초이기 때문에 널널하다.

코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())  # 달걀 수, 고객 수
P = [int(input()) for _ in range(M)]  # 고객이 제시한 가격

price = 0  # 최소 가격
max_profit = 0  # 최대 수익

for p in sorted(set(P), reverse=True):  # 큰 순서대로 정렬, 중복 값 제거
    profit = (
        len([x for x in P if x >= p]) * p  # 달걀이 고객보다 많으면 달걀수 * 가격
        if N >= len([x for x in P if x >= p])
        else N * p
    )
    if profit >= max_profit:
        price = p
        max_profit = profit


print(price, max_profit)

코드 설명

최대 수익 중 가장 낮은 가격을 책정해야 하므로 P를 내림차순으로 정렬한다. 그리고 set 함수로 중복 값 검사를 피해준다.

정렬된 리스트의 요소를 하나씩 꺼내면서 보다 높은 가격을 제시한 고객의 수를 구한다. 그 수가 달걀보다 많으면 profit에 고객의 수 * 가격을 저장하고 달걀이 더 많으면 달걀의 수 * 가격 을 저장한다.

가격과 수익을 최대값과 비교하면서 바꿔준다.