[백준 13904번] [Kotlin] 과제

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

13904번: 과제

 

난이도 : 골드 3
태그 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐

 

 

설명

과제는 마감일이 있고,

과제 하나를 끝내는 데에는 하루가 걸립니다.

과제를 풀 때마다 각기 다른 점수를 얻을 수 있을 때, 점수의 최댓값을 구하는 문제입니다.

 

 

어려운 것 같지만 천천히 접근해봅시다.

최댓값을 구하려면, 어떤 숙제를 해야 할까요?

바로 점수가 높은 숙제부터 하는 것입니다.

 

그럼 숙제를 언제 해야 할까요?

각 숙제는 마감일 안에 언제든지 하면 됩니다.

마감일이 5일 이내인 숙제가 있다면,

1, 2, 3, 4, 5일 중 언제해도 무방합니다.

백준의 예제를 봅시다.

마감일이 1일인 과제 1개, 마감일이 2일인 과제 1개, 마감일이 3일인 과제 1개,

마감일이 4일인 과제 3개, 마감일이 6일인 과제 1개가 있습니다.

 

그럼, 일자에 따라 할 수 있는 과제는 몇개일까요?

1일차에는 7개 모두,

2일차에는 6개 (마감일이 1일인 과제는 못함)

3일차에는 5개 (마감일이 1, 2일인 과제는 못함)

4일차에는 4개 (마감일이 1, 2, 3일인 과제는 못함)

5일차에는 1개 (마감일이 1, 2, 3, 4일인 과제는 못함)

6일차에는 1개 (마감일이 1, 2, 3, 4, 5일인 과제는 못함)

일차가 늘어날 수록 할 수 있는 과제가 적어집니다.

즉, 과제의 마감일 혹은 마감일에 최대한 가깝게 과제를 해야 합니다.

 

 

 

 

소스코드

import java.util.*

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

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

    val pq = PriorityQueue<Homework>(compareBy { -it.score })

    repeat(n) {
        val st = StringTokenizer(readLine())
        pq.add(Homework(st.nextToken().toInt(), st.nextToken().toInt()))
    }

    var answer = 0

    val visited = Array(pq.maxOf { it.day } + 1) { false }

    while (pq.isNotEmpty()) {
        val target = pq.poll()

        var day = target.day

        while (day > 0) {
            if (!visited[day]) {
                visited[day] = true
                answer += target.score
                break
            }
            day--
        }
    }

    println(answer)
}

 

 

위 접근방법을 코드로 표현한 것 입니다.

우선순위 큐를 점수가 높은 순으로 정렬하고,

 

큐에서 하나씩 꺼냅니다.

visited 배열은 각 날짜를 뜻하며, true는 과제를 한 날, false를 과제를 아직 하지 않은 날 입니다.

 

마감일이 5일인데, 4, 5일이 이미 과제를 했다면 그 다음으로 마감일(5일)에 가까운 날인 3일에 과제를 하는 식입니다.

1일 ~ 마감일 기간 내 과제가 가능한 날이 없다면, 해당 과제는 버립니다.

 

 

 

후기

점수 높은 순 정렬은 꽤 빠르게 떠올렸는데,

visited 배열을 하나 두고 마감일에 최대한 가깝게 과제를 한다는 아이디어를 떠올리는데 다소 시간이 걸린 문제였습니다.

꽤 재밌던 문제였던 것 같네요.