[solved.ac 실버1] 23559_밥 (파이썬, 그리디, 정렬)

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

 

문제

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

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

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

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

입력

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

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

출력

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

예제

---

나의 풀이

문제를 어떻게 접근해야 할 지 고민을 많이 한 문제이다. 직감적으로 1000원짜리와 5000원짜리 중 가치가 더 높은 것을 기준으로 정렬해야 한다고 생각했는데 그 가치를 어떻게 구체화 할 지 고민했다.

우선 문제에서 N일동안 매일 두 메뉴 중 하나를 골라서 먹는다고 했기 때문에 못 먹는 날은 없어야 한다. 문제에서 직접적인 언급은 없었지만 최소한 못 먹는 날이 없도록 입력이 주어진다고 생각하고 문제를 풀어야 했다.

문제는 어떠한 정렬 기준으로 정렬을 한다고 했을 때 5천원짜리 밥을 고른 날이 많아져서 예산을 초과해버리면 못 먹는 날이 발생할 수가 있다. 그래서 적어도 모든 날 밥을 먹게 하기 위해서 모든 날을 1000원 짜리 밥을 먹는 것으로 시작했다.

이렇게 모든 날 밥을 먹을 수 있도록 보장한 후에 예산이 남았고 5000원 짜리 밥을 먹을 정도로 충분하면서 1000원짜리 밥을 먹는 것보다 더 나은 선택이 될 때 1000원짜리 밥이 아닌 5000원짜리 밥을 선택하도록 한다.

그럼 어떤 날의 식사를 5000원짜리로 먹어야 할까? (즉, 어떻게 정렬을 해야할까?)

정렬의 기준을 5000원짜리 밥의 가치 - 1000원짜리 밥의 가치로 정했다. 이 가치를 기준으로 해서 내림차순 정렬을 하면 4000원을 더 투자했을 때 얻을 수 있는 가치 순으로 확인할 수 있다.

1000원짜리 밥을 5000원짜리 밥으로 바꾸는 과정을 예산이 있을 때까지 진행하지만 만약 1000원짜리 밥의 가치가 더 높아지는 경우 5000원짜리로 바꿀 이유가 없다. 즉, 예산이 충분하고, 5000원짜리 밥의 가치가 더 높을 때까지 5000원짜리 밥으로 바꿔주는 과정을 반복하면 최고의 메뉴를 먹을 수 있게 된다!

 

n, x = map(int, input().split())
bob = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda b: (b[0] - b[1]), reverse=True)
x -= 1000 * n # 천 원짜리 전부 구매
answer = sum([i[1] for i in bob]) # 천 원짜리 합
for b in bob:
    if x >= 4000 and b[0] > b[1]:
        answer += b[0] - b[1]
        x -= 4000
    else:
        break
print(answer)

bob은 크기가 2인 리스트들의 리스트이다. 각 항목의 0번째 인덱스는 5000원짜리의 가치, 1번 인덱스는 1000원짜리의 가치이다. 정렬 기준을 0번 인덱스 - 1번 인덱스로 하고, 내림 차순으로 정렬해 준비한다.

그리고 예산에서 천원 짜리로 모두 산 경우를 생각해 1000 * n 만큼 빼준다.

answer은 천원짜리 밥의 가치를 모두 더한 값으로 초기화한다.

이제 bob을 순회하며 예산이 4000원 이상이고, 5000원짜리 밥의 가치가 더 높을 동안 5000원짜리 밥으로 교체해주는 것이다.

answer에는 이미 천원짜리 가치가 다 더해진 상태이므로 5000원짜리의 가치에서의 차 만큼 더해주고, x도 마찬가지로 이미 천원짜리 밥을 구매한 경우이므로 추가로 4000원 만큼을 더 사용하는 것이다.

 

모든 과정이 끝나면 answer에는 정답이 남게 된다

채점 결과