[백준/Python] 23559번 : 밥

문제

 

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

 

---

Algorithm

• 그리디 알고리즘, 정렬

일반적으로 A를 선택하는 것이 더 최선일 것이라 가정하고,
예외적으로 B가 최선인 경우, 그리고 금액에 맞도록 선택 횟수를 조정 한 뒤,
메뉴를 1. A, B의 차이가 최대 2. A의 맛, 3. B의 맛을 기준으로 내림차순하여 그리디하게 선택한다.

 

---

 

 

Code

input = __import__('sys').stdin.readline

N,X = map(int, input().rstrip().split())
menu_list = [list(map(int, input().rstrip().split())) for i in range(N)]
cnt_A, cnt_B = 0, 0
ans = 0

for i in menu_list :
    if i[0] <= i[1] :
        cnt_B += 1
cnt_A = N - cnt_B
while cnt_A * 5000 + cnt_B * 1000 > X :
    cnt_A -= 1
    cnt_B += 1

menu_list.sort(key= lambda x : (-abs(x[0] - x[1]), -x[0], -x[1]))

for i in menu_list :
    if i[0] <= i[1] and cnt_B > 0 :
        ans += i[1]
        cnt_B -= 1
        continue
    if cnt_A == 0 and cnt_B > 0 :
        ans += i[1]
        cnt_B -= 1
        continue
    if cnt_A > 0 :
        ans += i[0]
        cnt_A -= 1
        continue
print(ans)

 

느낀 점

최선의 경우를 찾아내고 선택하려면 어떤 기준으로 해야할 지 미리 생각하고 하는 것이 중요함을 깨달았다. 처음 시도에서는 단지 A, B의 맛을 기준으로 정렬을 진행하여서 오답을 받았다. 이번 문제의 경우 결국 최대합을 구해야 함으로 두 선택간의 격차가 클 것들을 고를 수록 최대합을 구할 수 있었다.