백준 - 물건 팔기 (정렬, 완전 탐색) / Silver 3 / 1487번

문제 : https://www.acmicpc.net/problem/1487

1487번: 물건 팔기

 

풀이

import sys

n = int(sys.stdin.readline())

cost = []

for _ in range(n):  # [가격, 배달비] 형태로 생성.
    temp = list(map(int, sys.stdin.readline().split()))
    cost.append([temp[0], temp[1]])

cost.sort(key=lambda x: (x[0], x[1]))  # 가격, 배달비 순으로 정렬.

total = [0] * n  # 가격이 n일 때의 총이익.

for i in range(n):
    for j in range(i, n):  # 기준 가격 n
        benefit = cost[i][0] - cost[j][1]  # 가격은 기준 가격이지만 배달비는 원래 정해진대로.
        if benefit > 0:  # 이득일 경우에만 판다.
            total[i] += benefit

result = [cost[i][0] for i in range(n) if total[i] == max(total)]  # 최대 이익을 내는 기준 가격들 다모은다.

if sum(total) == 0:  # 이익을 내는 경우가 없다.
    print(0)
else:
    print(min(result))  # 최대 이익을 내는 기준 가격 중 제일 낮은거 출력.

[[가격1, 배달비1], [가격2, 배달비2], .....] 형태로 가격과 배달비를 하나로 묶어줘야 했으며

기준을 가격, 배달비 순으로 정렬 수행했다.

그래야 기준 가격보다 높은 것들을 기준 가격과  동일하게 처리할 수 있기 때문이다.

다만 배달비는 원래 배달비를 빼줘야 한다.

모든 경우에 이익이 0보다 작은 경우에는 total 배열에 변화가 없도록 구현하였다.