백준 23559 - 밥(Kotlin)

23559번: 밥

23559번: 밥

 

문제

제주대 학생회관 식당에는 두 개의 메뉴가 있다.

코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다.

 

준원이는 대면 수업이 시작되는 바람에 이제 남은 학기의 N일동안 매일 학식의 두 메뉴 중 정확히 하나를 골라서 먹어야 한다.

N일간의 두 메뉴는 이미 공지되어 있고, 준원이는 이미 모든 날의 각 메뉴가 얼마나 맛있을지 수치를 매겨 두었다.

 

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

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

 

---

입력

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

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

 

---

출력

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

 

---

알고리즘 분류

• 자료구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

 

---

해설

우선 이번 문제는 단순히 정렬만 잘하면 되는 문제였다.

 

이번 문제의 핵심은 A - B 를 기준으로 내림차순 정렬해야하며, 만약 그 차이가 같다면 A 를 기준으로 정렬해야한다.

 

왜 이렇게 풀어야할까?

우선 문제 속 인물 준원이는 모든 학식을 먹어야한다.

모든 학식을 먹기 위해서는 우선 기본적으로 1,000원짜리 음식을 먹는다고 가정해야 한다.

 

그렇다면 언제 5000원 짜리 음식을 먹어야할까?

5000원짜리 음식을 먹을만큼 돈의 여유가 있어야하며, A - B 의 만족도가 최고가 되는 날에 5000원짜리 음식을 먹어야한다.

그것이 바로 A - B 를 기준으로 정렬한 이유다.

 

이렇게 A - B 를 기준으로 정렬한 리스트를 순회하며 만약 그 차이가 음수라면 1000원짜리 음식을 먹어야 하며,

만약 그 차이가 양수이며, 5000원짜리 음식을 먹어도 남은 날 모든 음식을 1000원짜리 음식을 먹을 수 있다면 5000원짜리 음식을 먹어야 한다.

그것이 아니라면 1000원짜리 음식을 선택해야 한다.

 

---

전체 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var (cnt, price) = br.readLine().split(" ").map { it.toInt() }
    val list = mutableListOf<Pair<Int, Int>>()
    var ans = 0

    // Pair(5000원 음식 만족도, 1000원 음식 만족도)를 리스트에 추가.
    repeat(cnt) {
        val (price5000, price1000) = br.readLine().split(" ").map { it.toInt() }
        list.add(Pair(price5000, price1000))
    }

    // (A - B)를 기준으로 내림차순 정렬, 만약 그 차이가 같다면 A가 기준.
    val sortedList =
        list.sortedWith(compareByDescending<Pair<Int, Int>> { it.first - it.second }.thenByDescending { it.first })

    sortedList.forEachIndexed { idx, value ->
        // 앞으로 남은 날짜
        var day = cnt - idx - 1

        // A - B의 차이
        var gap = value.first - value.second

        // 차이가 음수라면 무조건 1000원짜리 음식 선택
        if (gap <= 0) {
            price -= 1000
            ans += value.second

            //만약 오늘 5000원짜리 음식을 먹었을 때 남은 날 모든 음식을 1000원짜리 음식을 먹을 수 있다면
        } else if (price - 5000 >= day * 1000) {
            price -= 5000
            ans += value.first
        }else{
            price -= 1000
            ans += value.second
        }
    }

    println(ans)
}

 

---

정답

 

사실 요즘 우선순위 큐 문제 위주로 풀다가 이번 문제를 푼 것이었는데 너무 우선순위 큐 문제에만 집착하다가 정답을 찾지 못하였따…😱

다른 분들의 해설을 보고 그냥 정렬 한방이면 풀리는 문제여서 당황했다…

오히려 너무 깊게 생각한게 이번 문제의 패착인가보다..⚡️