Python을 이용한 1487번 : 물건팔기에 대해서 포스팅하겠습니다. 1487번은 브루트포스 알고리즘로 분류되는 문제입니다.
1. 1487번 문제설명
- 입력
- 첫 번째 줄: 구매 의향이 있는 사람의 수 N (N ≤ 50)
- 두 번째 줄부터: 각 사람의 최대 지불 금액과 배송비 (각 값은 0 ≤ 최대 지불 금액, 배송비 < 10^6)
- 목표
- 세준이가 물건을 판매하여 최대 이익을 얻을 수 있는 가격을 찾아 출력합니다.
- 최대 이익이 여러 가격에서 발생하면 가장 낮은 가격을 출력합니다.
- 어떤 가격으로도 이익을 남길 수 없다면 0을 출력합니다.
- 출력
- 최대 이익을 만들어주는 가격 (이익이 최대인 가격이 여러 개라면 가장 낮은 가격) – 어떤 가격으로도 이익을 남길 수 없는 경우 0을 출력
2. 1487번 접근방법
- 정렬 : 구매자들을 지불할 최대 금액을 기준으로 오름차순 정렬합니다. 이 정렬은 이후에 가격을 설정할 때 높은 가격부터 고려할 수 있도록 도와줍니다. 정렬된 리스트를 통해 각 가격대에서의 최대 이익을 계산할 수 있습니다.
- 최대 이익 계산 각 가격대를 순회하며 이익을 계산합니다. 특정 가격을 설정하고 그 가격 이상 지불할 수 있는 구매자들에게 판매했을 때의 이익을 계산합니다. 이익 계산 시에는 판매 가격에서 각 구매자의 배송비를 뺀 값을 더합니다. 이를 통해 각 가격대에서의 순 이익을 구합니다.
3. 1487번 구현
3-1. 1487번 코드
Python
# https://www.acmicpc.net/problem/1487
from sys import stdin
# N명의 구매자 수를 입력받음
n = int(stdin.readline())
# 각 구매자의 최대 지불 금액과 배송비를 입력받아 리스트로 저장
buyers = list(map(lambda a : list(map(int,a.split())),stdin.readlines()))
# 최대 지불 금액을 기준으로 오름차순 정렬
buyers.sort(key=lambda a: a[0])
# 최대 이익을 저장할 변수 초기화
max_buyer = 0
# 최대 이익을 낼 수 있는 가격을 저장할 변수 초기화
index = 0
# 각 구매자의 최대 지불 금액을 가격으로 설정하고 이익을 계산
for i in range(n):
# 현재 가격을 구매자의 최대 지불 금액으로 설정
price = buyers[i][0]
# 이익을 계산하기 위한 변수 초기화
profit = 0
# 남은 구매자들을 순회하며 이익 계산
for j in range(i, n):
# 현재 가격이 구매자의 배송비보다 크면 이익에 추가
if price > buyers[j][1]:
profit += (price - buyers[j][1])
# 현재 계산된 이익이 최대 이익보다 크면 최대 이익과 가격 업데이트
if profit > max_buyer:
max_buyer = profit
index = buyers[i][0]
# 최대 이익을 낼 수 있는 가격 출력
print(index)