[JavaScript] 백준 23559 밥 (JS)

밥

📚 문제 설명

5,000원짜리 메뉴와 1,000원짜리 메뉴 2가지가 있다고 한다.
각각의 메뉴의 맛을 수치화하여 가지고 있다고 가정하자.
N 번의 식사를 X 원 이하의 돈으로 먹어야 할 때, 가장 맛있게 먹으면 맛의 합이 최대 몇인가.

👨🏻‍💻 풀이 과정

이 문제에서 생각해야할 점은 기본적으로 1,000원의 음식을 먹는다고 생각하고,
4,000원의 추가 비용을 냈을 때, 최고의 가성비를 찾는 것이다.

예를 들어 5,000원짜리 음식을 1번 먹는다고 가정했을 때,
5,000원 음식의 맛 - 1,000원 음식의 맛
이 최대가 되는 경우에 먹는 것이 최선의 방법이다. (5,000원 음식이 1,000원 음식보다 맛있을 경우)

따라서 전체 로직은 다음과 같이 구성하였다.

• 두 메뉴 맛의 차이가 오름차순이 되도록 정렬.
• 만약 돈이 있고 비싼 메뉴가 더 맛있다면.
  • 비싼 메뉴를 먹고 돈을 소비.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let [N, Budget] = input.shift().split(' ').map(Number);
    const MENU = input.map(v => v.split(' ').map(Number));
	// 맛이 차이가 오름차순으로 오도록 정렬
    MENU.sort((a, b) => {
        let aGap = a[0] - a[1];
        let bGap = b[0] - b[1];
        return aGap - bGap;
    });
	// 기본적으로 1,000원의 메뉴를 먹는다고 가정. 비싼 메뉴를 먹을 여유 자금을 저장.
    let UpgradeCost = Budget - (1000 * N);
	// 맛의 합을 계산할 변수
    let answer = 0;
	// 밥을 먹어야하는 일 수 만큼 반복문.
    for (let i = 0; i < N; i++) {
        const PopMenu = MENU.pop();
      	// 만약 여유 자금이 있고, 비싼 메뉴가 더 맛있다면.
        if (UpgradeCost >= 4000 && PopMenu[0] > PopMenu[1]) {
                answer += PopMenu[0];
                UpgradeCost -= 4000;
        }else {
            answer += PopMenu[1];
        }
    }
    console.log(answer);

🧐 후기

우선 순위 큐 문제인줄 알고 풀려고 했는데 막상 풀어보니 이게 왜 우선 순위 큐 문제인지 잘 모르겠다.
물론 우선 순위 큐를 이용하여 풀면 풀 수 있지만, JavaScript 에서 우선 순위 큐를 직접 구현해야하는 번거로움이 있기 때문에 딱 한번만 정렬을 하면 되는 이런 문제에서는 굳이 사용할 필요가 없어 보인다.