백준(BOJ) 2258 정육점(Python)

문제 내용.

 

그리디 문제.

원하는 양의 고기를 살 수 없는 경우부터 살펴보면, 이는 당연히 모든 고기를 사도 무게가 부족한 경우일 것이다.

따라서 위의 경우는 제외해준다.

그 후에는 입력받은 고기들을 가격으로 오름차순 정렬한 뒤 무게로 내림차순 정렬해줬다.

문제에서는 어떤 고기를 샀을 때 해당 고기보다 싼 고기들만 가격을 내지 않고 가져갈 수 있으므로, 같은 가격의 고기들을 사는 경우 가장 무게가 많이 나가는 고기를 사는 것이 유리하기 때문에 위와 같이 정렬해줬다.

그 후에는 정렬된 순서대로 고기를 담으며 무게를 체크해줬다.

이때 현재까지 담은 고기의 무게가 목표 무게 이상인 경우, 목표 무게를 달성했을 때의 전체 가격 중 최솟값으로 ans를 수정해준다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

n,m=map(int,input().split())
s=0
L=[]
for i in range(n):
    a,b=map(int,input().split())
    s+=a
    L.append([a,b])
L.sort(key=lambda x:(x[1],-x[0]))
if s<m:
    print(-1)
else:
    s=0
    k=0
    check=L[0][1]
    ans=10e10
    for i in range(n):
        if L[i][1]==check:
            k+=L[i][1]
        else:
            k=L[i][1]
            check=L[i][1]
        s+=L[i][0]
        if s>=m:
            ans=min(ans,k)
    print(ans)

코테가 하루 남아버렸다.