[알고리즘] 밥 python (백준 23559)

문제

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

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

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

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

입력

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

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

출력

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

 

 

풀이 과정

1. 입력값 처리 및 기본 설정

• N과 X는 각각 학기가 남은 일수와 총 예산을 의미합니다.
• availableCount 변수는 5,000원짜리 메뉴를 선택할 수 있는 최대 횟수를 계산하여 저장합니다. 이를 통해 예산 내에서 최대한 비싼 메뉴를 선택할 수 있는 횟수를 정합니다.
• 각 날마다 5,000원짜리 메뉴와 1,000원짜리 메뉴의 맛의 점수 차이를 계산하여 리스트 board에 저장합니다.

2. 맛 차이에 따른 메뉴 정렬

• 5,000원 메뉴와 1,000원 메뉴의 맛의 점수 차이를 기준으로 내림차순으로 정렬합니다.
• 이렇게 하면, 맛 점수 차이가 큰 날부터 선택할 수 있게 되어, 5,000원 메뉴를 선택하는 것이 더 유리한 경우를 우선적으로 고려할 수 있습니다.

3. 최적의 메뉴 선택

• 정렬된 리스트에서 상위 availableCount만큼은 5,000원 메뉴를 선택하여 res에 더합니다.
• 그 외의 경우는 1,000원 메뉴를 선택하여 res에 더합니다.
• 이를 통해 예산 내에서 맛의 합을 최대화하도록 메뉴를 선택합니다.

4. 결과 출력

• 모든 계산이 완료된 후, 최종적으로 맛의 합이 저장된 res 값을 출력합니다.

 

 

import sys
input = sys.stdin.readline

def sol() :
    N, X = list(map(int, input().split()))
    availableCount = (X - 1000 * N) // 4000
    board = []
    for _ in range(N):
        a, b = list(map(int, input().split()))
        board.append((a, b, a - b))
    res = 0
    board = sorted(board, key= lambda x: x[2], reverse= True)
    res += sum(list(map(lambda x: x[0] if x[0] > x[1] else x[1], board[:availableCount])))
    res += sum(list(map(lambda x: x[1], board[availableCount:])))
    print(res)

sol()