백준 13904 과제

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

마감일 안에 받을 수 있는 최고 점수를 구하는 문제이다.

마감일이 x일인 문제는 1~x일 이내에 풀 수 있는 문제이므로 가능하면 x일에 푸는 것이 좋다는 생각이 들 것이다.

그리고 마감일이 x인 문제가 여러개라면, 문제들 중 가장 높은 점수를 획득할 수 있는 문제일을 x일에 푸는 것이 좋을 것이다.

그럼 이 방법으로 풀이 알고리즘을 구상해 보면 아래와 같다.

1. 모든 과제를 점수 내림차순으로 정렬한다.
2. 점수가 높은 순으로, 과제 마감일에 과제 점수를 획득하는 것으로 하되 이미 해당 마감일에 다른 점수가 있다면, 마감일을 앞으로 당기면서 넣는다.
3. 1일차 까지 당겼는데도 자리가 없다면 무시한다.

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

위 예시를 통해 넣어보자.

점수 내림차순으로 정렬하면 (4 60), (2 50), (4 40), (3 30), (1 20), (4 10), (6 5)이다.

과제들을 순서대로 순회하며

1. (4 60) - 4일차에 60점을 획득한다.
2. (2 50) - 2일차에 50점을 획득한다.
3. (4 40) - 4일차에 이미 60점을 얻었으므로 3일차에 40점을 획득한다.
4. (3 30) - 3일차와 2일차에 이미 점수를 얻었으므로 1일차에 30점을 획득한다.
5. (1 20) - 1일차에 30점을 얻었으므로 무시한다.
6. (4 10) - 1~4일차 모두 점수가 있으므로 무시한다.
7. (6 5) - 6일차에 5점을 획득한다.

따라서 60 + 50 + 40 + 30 + 5 = 185점을 획득한다.

import java.util.*

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()

    val homeworks = Array(N){
        val (e, s) = readLine().split(' ').map{it.toInt()}
        Homework(e, s)
    }.sortedWith{ h1, h2 ->
        h2.score - h1.score
    }

    val scores = IntArray(1001){0}

    for(hw in homeworks){
        if(scores[hw.deadLine] == 0){
            scores[hw.deadLine] = hw.score
        }else{
            var idx = hw.deadLine - 1
            while(idx > 0){
                if(scores[idx] == 0){
                    scores[idx] = hw.score
                    break
                }
                idx--
            }
        }
    }

    print(scores.sum())
}

data class Homework(
    val deadLine: Int,
    val score: Int
)