알고리즘
그리디
[23559] 밥
by Hwang
문제
https://www.acmicpc.net/problem/23559
풀이
N일간 한 번도 빠짐없이 식사를 해야하기 때문에 먼저 모든 선택을 1000원짜리 메뉴를 골랐다고 가정한 상태에서 시작합니다.
현재 상태에서는 두 가지의 경우가 나올 수 있습니다. 돈을 다 썼거나, 돈이 남은 경우가 존재합니다. 만약 돈을 다 썼다면 그대로 1000원 메뉴의 맛의 합을 출력해주면 되지만, 돈이 남는 경우는 5000원짜리의 메뉴를 선택할 수 있는 기회가 존재합니다.
따라서 남아있는 돈으로 현재 상태에서 맛의 합이 최대가 되도록, X를 넘지 않는 선에서 5000원짜리 메뉴로 바꾸는 과정이 필요한데, 맛의 합이 최대가 되도록 바꿔주기 위해서는 해당 날짜의 5000원짜리 메뉴와 1000원짜리 메뉴의 차이가 가장 큰 순서대로 바꿔주면 되겠죠? 그러나 무조건 바꾸는게 좋은 방법이 아닐 수도 있습니다. 5000원짜리 메뉴보다 1000원짜리 메뉴의 맛이 큰 경우가 존재할 수 있기 때문입니다.
따라서 메뉴를 바꿔줄 때 총 가격이 X를 넘지 않는지 확인 함과 동시에 5000원 메뉴가 1000원 메뉴의 맛보다 더 큰지 확인하는 과정이 필요합니다.
import sys
N, X = map(int, sys.stdin.readline().split())
menu = [tuple(map(int, sys.stdin.readline().strip().split()))
for _ in range(N)]
menu.sort(key=lambda x: (x[0]-x[1]), reverse=True)
X -= 1000 * N
result = 0
for i in range(N):
A, B = menu[i]
if X >= 4000 and A > B:
X -= 4000
B = A
result += B
print(result)
Comment