[BOJ/Python] 23559번: 밥

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

문제

제주대 학생회관 식당에는 두 개의 메뉴가 있다. 코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다.

준원이는 대면 수업이 시작되는 바람에 이제 남은 학기의 N일동안 매일 학식의 두 메뉴 중 정확히 하나를 골라서 먹어야 한다. N일간의 두 메뉴는 이미 공지되어 있고, 준원이는 이미 모든 날의 각 메뉴가 얼마나 맛있을지 수치를 매겨 두었다.

준원이는 N일간 학식에 총 X원 이하를 써야 한다.

여러분이 N일간 준원이의 메뉴를 잘 골라서, 고른 메뉴의 맛의 합을 최대화 해주자!

입력

첫째 줄에는 두 정수 N, X가 주어진다.

둘째 줄부터 N개의 줄에, 각 날에 먹을 수 있는 5,000원짜리 메뉴의 맛 A와 1,000원짜리 메뉴의 맛 B가 공백을 사이에 두고 주어진다.

출력

준원이가 고른 메뉴들의 맛의 합을 최대화했을 때의 값을 출력하라.

---

구상

우선, 삼일연속 같은 메뉴를 먹을 수 없다와 같은 제한이 없기때문에, 먹는 순서는 상관이 없을 거라 정렬을 써도 되겠다라는 생각이 들었다. 그리고, 밥을 굶는 선택지는 없기에 무조건 하루에 최소 천원은 쓰게 될 것이다. 그래서 오천원짜리를 먹느라 돈을 탕진하지 못하게 미리 날짜 수만큼 천원씩 빼두고, 오천원짜리 먹을때 사천원을 더 빼는 방식을 생각했다. 그래서 높은 만족도에 오천원 쓰는게 맞다 생각해서, 오천원짜리 맛을 우선순위로 정렬을 하였다.

코드

N,X=map(int,input().split())
arr=[]
s=0
for _ in range(N):
    x=list(map(int,input().split()))
    arr.append(x)

arr.sort(key=lambda x:x[1], reverse=True)
arr.sort(key=lambda x:x[0], reverse=True)

X-=N*1000 # 돈을 탕진하는걸 방지하기 위해 하루에 최소 천원씩은 무조건 써야되므로 미리 빼두기

for i in range(N):
    if arr[i][0] < arr[i][1]:
        s+=arr[i][1]
    elif X>=4000:
        s+=arr[i][0]
        X-=4000
    else:
        s+=arr[i][1]

print(s)

이렇게 하니 틀렸다. 왜 틀렸을까 생각해보니, 한 반례가 있었다. 오천원짜리는 한번밖에 못먹는 돈을 갖고 만족도가 51 50, 50 1 이 있다 하면 내 코드는 51과 1을 선택할 것이다. 하지만 50 , 50을 선택하는 것이 현명하다. 즉, 정렬을 위와 같이 하면 안되고 두 만족도의 차이로 해야된다.

N,X=map(int,input().split())
arr=[]
s=0
for _ in range(N):
    x=list(map(int,input().split()))
    arr.append(x)

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

X-=N*1000 # 돈을 탕진하는걸 방지하기 위해 하루에 최소 천원씩은 무조건 써야되므로 미리 빼두기

for i in range(N):
    if arr[i][0] < arr[i][1]:
        s+=arr[i][1]
    elif X>=4000:
        s+=arr[i][0]
        X-=4000
    else:
        s+=arr[i][1]

print(s)

이렇게 하니 맞았따

 

아 참고로 arr은 아래와같이 단순하게 짤수도 있다

arr=[list(map(int, input().split())) for _ in range(N)]

점점 파이썬 문법 알아가는 거 같아서 좋다