백준 1487 물건 팔기

Python을 이용한 1487번 : 물건팔기에 대해서 포스팅하겠습니다. 1487번은 브루트포스 알고리즘로 분류되는 문제입니다.

boj-1487-title

1. 1487번 문제설명

  • 입력
    • 첫 번째 줄: 구매 의향이 있는 사람의 수 N (N ≤ 50)
    • 두 번째 줄부터: 각 사람의 최대 지불 금액과 배송비 (각 값은 0 ≤ 최대 지불 금액, 배송비 < 10^6)
  • 목표
    • 세준이가 물건을 판매하여 최대 이익을 얻을 수 있는 가격을 찾아 출력합니다.
    • 최대 이익이 여러 가격에서 발생하면 가장 낮은 가격을 출력합니다.
    • 어떤 가격으로도 이익을 남길 수 없다면 0을 출력합니다.
  • 출력
    • 최대 이익을 만들어주는 가격 (이익이 최대인 가격이 여러 개라면 가장 낮은 가격) – 어떤 가격으로도 이익을 남길 수 없는 경우 0을 출력

2. 1487번 접근방법

boj-1487-diagram
  • 정렬 : 구매자들을 지불할 최대 금액을 기준으로 오름차순 정렬합니다. 이 정렬은 이후에 가격을 설정할 때 높은 가격부터 고려할 수 있도록 도와줍니다. 정렬된 리스트를 통해 각 가격대에서의 최대 이익을 계산할 수 있습니다.
  • 최대 이익 계산 각 가격대를 순회하며 이익을 계산합니다. 특정 가격을 설정하고 그 가격 이상 지불할 수 있는 구매자들에게 판매했을 때의 이익을 계산합니다. 이익 계산 시에는 판매 가격에서 각 구매자의 배송비를 뺀 값을 더합니다. 이를 통해 각 가격대에서의 순 이익을 구합니다.

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)

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

Scroll to Top