[파이썬] 백준 2258 : 정육점 (골드4)

[파이썬] 백준 2258 : 정육점 (골드4)

2258번: 정육점

---

문제

---

풀이

0. 방향성 생각

• 특정 가격 고기를 사면 싼 고기를 모두 고를 수 있다.
• table[가격]  = [무게1, 무게2, ...] 이런식으로 나타내서 무게 역순으로 정렬하기.
• 긴 배열에서 가격 연산을 줄이기 위해서 누적 합 사용.

1. 입력

from collections import defaultdict as dd
import sys
input = lambda : sys.stdin.readline().rstrip()

n,goal = map(int,input().split())
info = [list(map(int,input().split())) for _ in range(n)]

table = dd(list)
for w,p in info:
    table[p].append(w)

• 일단 무게 순으로 받기 위해서 defaultdict에 가격 추가해주기

2. 누적 합 만들어주기

table_sum = dd(list)
total_w = 0
for p in table:
    table[p].sort(reverse=True)
    for i in table[p]:
        if table_sum[p]:
            table_sum[p].append(table_sum[p][-1]+i)
        else:
            table_sum[p].append(i)
    total_w += table_sum[p][-1]

• table_sum에 누적 합 가격 저장해주기
• total_w에 정육점에서 파는 전체 무게 저장해주기

3. 출력

if total_w < goal:
    print(-1)
else:
    now = 0
    answer = []
    for p in sorted(table_sum.keys()):
        cumul = table_sum[p]
        if now + cumul[-1] < goal:
            now += cumul[-1]
        else:
            for count,w in enumerate(cumul):
                if now + w >= goal:
                    answer.append(p*(count+1))
                    break
            now += cumul[-1]
    print(min(answer))

• 정육점에서 파는 전체 무게보다 목표로 하는 무게가 크면 -1 출력
• 그렇지 않은 경우에는 현재 구매한 고기의 양을 나타낸 now, 정답 후보를 넣을 answer 리스트 정의
• 현재 가격으로 판매하는 모든 고기(cumul[-1])를 구매해도 goal에 못미치는 경우, 고기를 무료로 받는다.
  (현재 가격 p보다 비싼 고기를 구매하는 순간 공짜로 얻을 수 있다.)
• 현재 가격으로 판매하는 모든 고기를 구매해 goal을 달성하는 경우, 현재 가격으로 판매하는 고기를 하나씩 탐색한다.
• cumul에는 누적 고기무게가 저장되어있다,
• now에 현재 누적 고기량 w을 더해서 goal에 달성하는 경우 현재 고기까지만 구매한 후 고기를 몇 개 샀는지 계산 (인덱스 count+1를 통해서 몇 개 샀는지 계산한다)
• 특정 가격대의 고기를 사서 goal을 만족했더라도, 더 비싼 고기를 사서 더 적은 비용으로 고기를 살 수 있는 경우가 있으므로 끝까지 순회해주기.
  이를 위해서 특정 가격대의 탐색이 끝나면 현재 구매한 고기 now에 cumul[-1] (가격대 고기 전부)를 더해준다.

 

---

전체코드

from collections import defaultdict as dd
import sys
input = lambda : sys.stdin.readline().rstrip()

n,goal = map(int,input().split())
info = [list(map(int,input().split())) for _ in range(n)]

table = dd(list)
for w,p in info:
    table[p].append(w)

table_sum = dd(list)
total_w = 0
for p in table:
    table[p].sort(reverse=True)
    for i in table[p]:
        if table_sum[p]:
            table_sum[p].append(table_sum[p][-1]+i)
        else:
            table_sum[p].append(i)
    total_w += table_sum[p][-1]

if total_w < goal:
    print(-1)
else:
    now = 0
    answer = []
    for p in sorted(table_sum.keys()):
        cumul = table_sum[p]
        if now + cumul[-1] < goal:
            now += cumul[-1]
        else:
            for count,w in enumerate(cumul):
                if now + w >= goal:
                    answer.append(p*(count+1))
                    break
            now += cumul[-1]
    print(min(answer))

 

코멘트

마땅한 풀이가 생각 안나서 일주일쯤 고민한듯....