[백준/BOJ] 13904번: 과제

문제

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

13904번: 과제

해설

우선순위 큐를 이용한 그리디 알고리즘으로 문제를 풀었다.

문제의 예시를 보자.

다음과 같이 점수가 더 큰 문제부터 차례대로 정렬을 해놓았다.

우선 점수가 가장 큰 60점짜리 문제는 4일이 마감 기간이므로 4일에 문제를 풀도록 하자.

이제 다음으로 점수가 높은 50점짜리 문제를 보자.

이 문제 또한 2일째에 아직 아무 계획이 없으므로 2일째에 끝내도록 하자.

다음으로 40점짜리 문제이다.

이 문제의 마감기한은 4일이지만, 이미 4일 째에 60점짜리 문제를 끝내도록 정해놨다.

그러므로 3일 째에 문제를 끝내면 된다.

이제 어떻게 진행될지 눈에 보일 것이다.

30점짜리 문제는 1일 차에 끝내야만 한다.

1일 차에 30점 문제를 처리한다.

20점 문제와 10점 문제는 마감기한 내에 더 점수가 큰 문제들을 풀어야 하므로 처리하지 못한다.

즉, 버리면 되는 문제들이다.

5점 문제는 마감기한이 6일까지이다.

6일에는 아무 계획이 없으므로 6일에 문제를 끝내도록 하자.

결론적으로 다음과 같은 표를 얻을 수 있다.

결론적으로 가장 많은 점수를 얻는 방법은 30 + 50 + 40 + 60 + 5 = 185가 된다.

코드

import java.util.*
import kotlin.math.max

private val pq = PriorityQueue<Info>()
private var maxDeadLine = 0

data class Info(val deadLine: Int, val score: Int): Comparable<Info> {
    override fun compareTo(other: Info): Int = score - other.score
}

fun main() {
    input()
    println(totalScore())
}

private fun totalScore(): Int {
    val getScore = IntArray(maxDeadLine + 1)

    while(pq.isNotEmpty()) {
        val curProblem = pq.poll()
        val curProblemDeadLine = curProblem.deadLine
        val curProblemScore = curProblem.score

        for(i in curProblemDeadLine downTo 1) {
            if(getScore[i] < curProblemScore) {
                getScore[i] = curProblemScore
                break
            }
        }
    }

    var total = 0
    for(i in 1 .. maxDeadLine) {
        total += getScore[i]
    }

    return total
}

private fun input() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    repeat(n) {
        val (deadLine, score) = readLine().split(" ").map { it.toInt() }
        maxDeadLine = max(maxDeadLine, deadLine)
        pq.add(Info(deadLine, score))
    }
}