두 종류 물건을 특정 개수만큼 사면서 최소 가격에 사는 그리디 알고리즘

1. 문제

 

30022번: 행사 준비 (acmicpc.net)

30022번: 행사 준비

 

2. 풀이

 

첫번째 상점 가격을 오름차순 정렬하고, A개만큼 산 다음, 두번째 상점 가격을 오름차순 정렬해서,

 

이미 산 아이템일때, 첫번째 상점 가격보다 저렴한지 비교해서 저렴하면 두번째 상점 것으로 사보고..

 

아니면 첫번째, 두번째 합쳐서 정렬해서 처음부터 순회할때, A개를 맞추면 나머지는 두번째 상점에서 다 사고

 

B개를 맞추면 나머지는 첫번째 상점에서 다 사고..

 

아무튼 별 생각을 다 해봤는데 계속 틀리더라

 

해법은 일단 첫번째 상점의 아이템 p1,p2,...,pn을 전부 사고

 

두번째 상점과 첫번째 상점 가격차이 q1-p1, q2-p2,..., qn-pn를 구한 다음 얘들을 오름차순으로 정렬하면...

 

$q_{i_{1}} - p_{i_{1}} < q_{i_{2}} - p_{i_{2}} < ... < q_{i_{n}} - p_{i_{n}}$

 

여기서 작은것부터 b개를 고른다면...?

 

일정한 상수 $s = (p_{1} + p_{2} + ... + p_{n})$에 대하여, 차이들 중 가장 작은 값 부터 1개씩 더해 총 b개를 더하면...

 

$(p_{i_{b+1}} + p_{i_{b+2}} + ... + p_{i_{n}} + q_{i_{1}} + q_{i_{2}} + ... + q_{i_{b}}$가 될거고,

 

두번째 상점에서 b개를 사고 첫번째 상점에서 a개를 산 가격이 되면서,

 

일정한 상수 s에서 가장 작은 값들을 차례대로 더해 나갔기 때문에, 이 값이 최소이다.

 

#종류 1을 A개 종류 2를 B개 사면서, 가격 합이 최소가 되는 그리디 알고리즘
from sys import stdin

n,a,b = map(int,stdin.readline().split())

A = []

answer = 0

#종류 1을 N개 모두 사고, p1+p2+..+pn = s 일정한 상수
#종류 2와 종류 1의 차이 q1-p1, q2-p2,...,qn-pn을 오름차순 정렬
#여기서 작은것부터 b개씩 더하면, 일정한 상수에 최솟값들을 더해나갔으므로, 전체 합은 최소가 되며
#q1+q2+..+qb + p1+p2+...+pa로 p가 a개 q가 b개가 된다.

for i in range(n):

    p,q = map(int,stdin.readline().split())

    answer += p

    A.append(q-p)

A.sort()

for i in range(b):
    
    answer += A[i]

print(answer)

 

어렵다...