1487. [Python]물건 팔기

1. 문제

 

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

1487번: 물건 팔기

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 브루트포스

 

3. 파이썬 코드

 

N = int(input())
# 가격을 저장할 리스트
price_list = []
# 이득을 저장할 리스트
gain_list = []
# 가격을 리스트 형태로 리스트에 저장
for _ in range(N):
    num = list(map(int,input().split()))
    price_list.append(num)
# 리스트를 오름차순 정렬
price_list.sort()
# 안파는 경우를 체크할 변수
check = 0
# N의 길이만큼 반복문 시행
for i in range(len(price_list)):
    # 각 반복문마다 이득을 계산할 변수
    total = 0
    # i번 가격과 i~N까지 배송비를 빼고 이득에 더해가며 총 이득 계산
    for j in range(i,N):
        gain = price_list[i][0] - price_list[j][1]
        # 음수인 경우 안파는게 이득이다.
        if gain <= 0:
            total += 0
        else:
            total += gain
    # 만약 이득이 0 인경우 check라는 변수를 통해서 안파는 것을 체크함
    if total == 0:
        check += 1
    # 총합을 gain_list 라는데 추가함
    gain_list.append(total)
# 제일 높은 이득을 변수로저장
max_value = max(gain_list)
# check 라는 변수를 통해서 아무한테도 안판 것을 확인한 후 다르면 제일 높은 이득이 나온 값을 출력
if check != N:
    for i in range(N):
        if gain_list[i] == max_value:
            print(price_list[i][0])
            break
else:
    print(0)

 

4. 문제를 풀고난 후 생각

 

• 문제를 보고 이해를 잘못하여 생각을 좀 깊게 했던 문제이다.
• 처음엔 그저 단순하게 계산값 - 배송비 를 통해서 이익을 내는 것이라고 생각했지만 예제의 정답이 들어맞지 않아서 어떤 구조로 이익을 도출하는지 생각을 했었고, 각 금액마다 적용하여 그 금액에서 각자 최대 지불할 수 있는 금액보다 작으면 배송비를 빼주는 식으로 모든 값에 대해서 계산을 해줬다.
• 답을 내기 위해서 가격을 오름차순 정렬을 먼저 진행해줬다.

- 예시로 아래와 같이 구매자가 있을 경우
1. 13 5
2. 17 7
3. 10 5

금액,배송비 / 가격	10	13	17
10, 5	10 - 5 = 5	X(가격이 최대금액을 넘음)	X(가격이 최대금액을 넘음)
13, 5	10 - 5 = 5	13 - 5 = 8	X(가격이 최대금액을 넘음)
17, 7	10 - 7 = 3	13 - 7 = 6	17 - 7 = 10
총 이익	5 + 5 + 3 = 13	8 + 6 = 14	10

• 위의 표처럼 각자 가격에 대해서 모든 이득을 구해서 저장한 후 그 중 최대의 이익이 나오는 경우에 가격을 출력해주는 것으로 문제를 해결하였다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 브루트포스