(Python/파이썬) - 백준(BOJ) 2258번 : 정육점

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

2258번: 정육점

---

• 문제 : 

은혜는 정육점에서 고기를 사려고 한다. 보통 정육점에서는 자신이 원하는 양을 이야기하면 그 양만큼의 고기를 팔지만, 은혜가 방문한 정육점에서는 세일 행사를 하고 있었기 때문에 N 덩어리의 고기를 이미 잘라놓고 판매하고 있었다.

 

각각의 덩어리들은 이미 정해져 있는 무게와 가격이 있는데, 어떤 덩어리를 샀을 때에는 그 덩어리보다 싼 고기들은 얼마든지 덤으로 얻을 수 있다(추가 비용의 지불 없이). 또한 각각의 고기들은 부위가 다를 수 있기 때문에 비용과 무게와의 관계가 서로 비례하는 관계가 아닐 수도 있다. 은혜는 이러한 점을 고려하지 않고, 어느 부위든지 자신이 원하는 양만 구매하면 되는 것으로 가정한다. 또한 만약 가격이 더 싸다면 은혜가 필요한 양보다 더 많은 고기를 살 수도 있다.

 

각 덩어리에 대한 정보가 주어졌을 때, 은혜가 원하는 양의 고기를 구매하기 위해 필요한 최소 비용을 계산하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

그리디하게 해결할 수 있는 문제입니다.

 

사려는 덩어리보다 "싼" 고기들만 무료로 받을 수 있다는 점이 이 문제의 핵심입니다.

예를 들어, 아래와 같은 input이 입력되었을 때

 

3 2
1 5
1 5
2 6

 

10원을 지불하여 1 + 1 의 고기를 사는 것보다 6원을 지불하여 2의 고기를 사는 것이 효율적입니다.

처음엔 총 합이 M 이상일 때 고기의 가격을 출력했는데 위의 예제가 반례로 작용하여 다르게 풀어보았습니다.

 

풀이 흐름입니다.

 

1.  고기의 가격 오름차순, 가격이 같다면 무게 내림차순으로 정렬

 

2. 가장 싼 고기 하나만 사도 무게를 충족한다면 가장 싼 고기의 가격을 출력하고 종료.

 

3. 두 번째 고기부터 마지막 고기까지 탐색하며 같은 가격의 고기에 대한 정보(인덱스값)을 tmp 배열에 저장

이는 위의 에제에서 2라는 M값을 만들기 위해 5+5가 저렴한지, 아니면 그 다음으로 비싼 고기인 6원짜리 고기까지 사는저렴한지 비교하기 위한 값

 

4. 현재 탐색하는 고기까지 사면 M 이상인 경우, 두 가지 경우중 더 낮은 값 하나를 선택해야 함

 

- 현재 탐색하는 고기와 같은 가격의 고기들을 전부 더한 가격

- 다음으로 비싼 고기의 가격

 

A. (tmp에 있는 고기의 가격 x tmp의 길이) = (현재 탐색중인 고기를 사는 가격)

B. while문을 통해 마지막 인덱스까지 탐색하며 찾은 다음으로 비싼 고기 가격

 

A와 B값을 비교하여 더 낮은 값을 출력하면 됩니다.

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
price = sorted([list(map(int,input().split())) for _ in range(N)], key = lambda x : (x[1],-x[0]))
if price[0][0] >= M: # 가격이 제일 싼 고기 하나만 사도 만족하는 경우
    print(price[0][1])
    exit()
s = price[0][0]
tmp = [0] # 같은 가격의 고기들의 인덱스를 저장하기 위함
for i in range(1,N):
    s += price[i][0]
    if price[tmp[-1]][1] == price[i][1]:
        tmp.append(i)
    else:
        tmp = [i]
    if s >= M:
        if price[i-1][1] < price[i][1]: # 현재 사려는 고기까지 사면 M을 충족하며, 그 전 고기의 가격이 현재 사려는 고기보다 싼 경우
            print(price[i][1])
            exit()
        else: # 현재 사려는 고기와 같은 가격의 고기가 여러개일 경우
            total_price = 0 
            for j in tmp: # 같은 가격의 고기를 전부 사는 경우
                total_price += price[j][1]
            while i < N and price[j][1] ==  price[i][1]: # 그 다음으로 비싼 고기를 사는 가격
                i += 1
            if i < N: # 그 다음으로 비싼 고기가 있다면
                print(min(price[i][1], total_price)) # 같은가격의 고기를 모두 사는것 vs 그 다음으로 비싼 고기를 사는 것 비교 
            else:
                print(total_price) # 다음으로 비싼 고기가 없으면 어쩔 수 없이 같은가격의 고기를 사야됨
            exit()

print(-1)