https://www.acmicpc.net/problem/1781
N개의 문제가 주어지고, 각 문제는 데드라인과 보상인 컵라면 개수가 주어진다.
문제를 풀어 받을 수 있는 컵라면의 최대 개수를 출력하는 문제이다.
문제들은 데드라인이 있어, 데드라인이 X인 문제는 1일~X일 사이에 풀 수 있다.
이 점을 생각해 그리디하게 문제를 풀 수 있는 알고리즘을 생각해보았다.
1. 먼저 입력받은 문제들을 데드라인의 내림차순으로 (같을 경우 보상이 많은 순서대로) 정렬한다.
데드라인 내림차순으로 한 이유는 데드라인이 긴 문제의 경우 최대한 데드라인에 맞춰 푸는 것이 최적의 경우가 될 것 같다 생각했기 때문이다.
따라서 내림차순을 통해 데드라인이 긴 (같으면 컵라면이 많은) 문제들부터 풀도록 하였다.
2. 최대 reward(컵라면)를 반환하는 Priority Queue를 준비한다.
현재 문제의 deadline 날짜에 이미 다른 문제를 푼 경우(더 높은 reward) 해당 문제는 PQ에 넣어 다른 날짜에 풀 수도 있도록 하기 위해서이다.
1번 예시와 동일하게 (1 3) (2 10) (2 20)이 들어오면, (2 20)을 2일에 풀고, (2 10)은 PQ에 넣은 뒤 1일에 (1 3)을 PQ에 넣고 (2 10)을 꺼내 풀게 된다.
3. 날짜를 1일씩 줄여 가며 다음 과정을 반복한다.
현재 날짜 <= 현재 문제 deadline인 경우:
현재 문제를 pq에 넣고, 현재 문제의 deadline에 문제를 풀었는지 확인한 뒤, 안풀었으면 해당 날짜에 풀고 풀었으면 다음 문제로 이동.
현재 날짜 > 현재 문제 deadline인 경우:
현재 날짜에 pq에서 꺼내온 문제를 풀고 날짜를 감소시킴.
위 과정을 모든 문제에 대해 진행한 뒤, 남아 있는 day만큼 pq에서 꺼내 와 풀어 reward(컵라면)를 추가함.
예제를 통해 알고리즘을 따라가 보자.
7
6 2
4 5
4 4
4 2
3 1
1 7
1 6
위와 같은 케이스가 있다고 하자. (deadline, reward 내림차순 했다 가정)
-
day 6에서 시작한다.
(6 2)에 대해, 6 <= 6이므로 PQ에 (6 2)를 넣고 6일차에 푼 문제가 없으므로 PQ에서 꺼내 6일차에 reward 2를 획득하고 day-- idx++ -
day 5
(4 5)에 대해, 5 > 4이므로 PQ에 넣지 않음.
5일차에 푼 문제가 없으므로 PQ에서 문제를 꺼내 와 5일차에 풂. 단 PQ가 비었으므로 reward를 추가하지는 않고 day-- -
day 4
(4 5)에 대해, 4 <= 4이므로 PQ에 (4 5)를 넣고 4일차에 푼 문제가 없으므로 PQ에서 꺼내 4일차에 reward 5를 획득하고 day-- idx++ -
day 3
(4 4)에 대해, 3 <= 4이므로 PQ에 (4 4)를 넣음. 4일차에 이미 reward 5짜리 문제를 풀었으므로 PQ에 넣기만 한 상태로 idx++ -
day 3
(4 2)에 대해, 4번 과정과 동일하게 PQ에 (4 2)만 넣고 idx++ -
day 3
(3 1)에 대해, 3 <= 3이므로 PQ에 (3 1)을 넣음. 3일차에 푼 문제가 없으므로 PQ에서 (4 4)를 꺼내 3일차에 풀어 reward 4 획득하고 day-- idx++ -
day 2
(1 7)에 대해 2 > 1이므로 PQ에 넣지 않음. 2일차에 푼 문제가 없으므로 PQ에서 (4 2)를 꺼내 2일차에 풀어 reward 2 획득. day-- -
day 1
(1 7)에 대해 1 <= 1이므로 PQ에 넣음. 1일차에 푼 문제가 없으므로 PQ에서 (1 7)을 꺼내 1일차에 풀어 reward 7 획득. day-- -
남은 day가 0이므로 추가 작업은 필요하지 않음. answer 20 출력.
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val N = readLine().toInt()
val problems = Array(N){
val (dl, cup) = readLine().split(' ').map{it.toInt()}
Problem(dl, cup)
}.sortedWith{ p1, p2 ->
if(p1.deadline == p2.deadline) p2.reward - p1.reward
else p2.deadline - p1.deadline
}
val pq = PriorityQueue<Problem>{p1, p2 -> p2.reward - p1.reward}
var answer = 0
var day = problems.maxOf{it.deadline}
var idx = 0
val dayCheck = IntArray(N + 1){0}
while(idx < problems.size){
val p = problems[idx]
if(day <= p.deadline){
pq.offer(p)
}else{
pq.poll()?.let {
dayCheck[day] = it.reward
answer += it.reward
}
day--
continue
}
if(dayCheck[p.deadline] == 0){
pq.poll()?.let {
dayCheck[p.deadline] = it.reward
answer += it.reward
}
day = p.deadline - 1
}
idx++
}
while(day > 0){
pq.poll()?.let {
dayCheck[day--] = it.reward
answer += it.reward
}
}
print(answer)
}
data class Problem(
val deadline: Int,
val reward: Int
)+) 추가로
얼마 전에 풀었던 다른 그리디 문제와 유사한 방법이 생각나서 적어본다.
입력 문제들을 컵라면 개수의 내림차순으로 정렬한다.
그리고나서 문제들을 순회하며, 해당 deadline 날짜에 문제를 풀지 않았다면 우선적으로 그 날짜에 풀고 해당 deadline 날짜에 풀었다면 그 날짜부터 앞으로 이동하며 빈 날짜에 푼다.
단, 이 문제에서는 N이 200,000까지 이므로 선형으로 빈 날짜를 찾는다면 시간 초과가 날 수 있다.
그래서 다음 빈 날짜를 가리키도록 union-find 알고리즘을 이용해 시간을 단축시켜 풀 수 있다.
lateinit var dt: IntArray
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val N = readLine().toInt()
val problems = Array(N){
val (dl, cup) = readLine().split(' ').map{it.toInt()}
Problem(dl, cup)
}.sortedWith{ p1, p2 -> p2.reward - p1.reward }
val dayCheck = IntArray(N + 1){0}
dt = IntArray(N + 1){it}
for(p in problems){
if(dayCheck[p.deadline] == 0){
dayCheck[p.deadline] = p.reward
union(find(p.deadline) - 1, p.deadline)
}else{
val parent = find(p.deadline)
if(parent > 0) {
dayCheck[parent] = p.reward
union(parent - 1, p.deadline)
find(p.deadline) // union 후 싱크 맞추기
}
}
}
print(dayCheck.sum() - dayCheck[0])
}
fun find(x: Int): Int{
if(dt[x] == x) return x
dt[x] = find(dt[x])
return dt[x]
}
fun union(x: Int, y: Int){
dt[find(y)] = find(x)
}
data class Problem(
val deadline: Int,
val reward: Int
)복잡하지 않고 훨씬 좋은 방법인 것 같다.
