BOJ 28068 | I Am Knowledge

정답 비율이 지나치게 낮은 것이 눈에 띕니다. 그리고 그럴 만 합니다.

이 문제는 정렬 후 순회하면서 $O(N)$에 처리하는 그리디의 전형적인 유형입니다. 그러나 정렬하는 과정이 생각이 많이 필요하고, 코드는 단순하나 생각이 단순하지 않은 문제입니다. 근데 풀고 나면 엄청 간단합니다.

책은 두 가지 정보를 담고 있습니다. $cost, reward$라고 합시다.

책을 읽기 위해서는 $cost$만큼의 즐거움이 소모되고, 책을 읽고 난 후에는 $reward$만큼의 즐거움을 받습니다.

그렇다면 책은 두 가지 종류로 나뉩니다. 바로 $cost \leq reward$인 책과 $cost > reward$인 책입니다.

전자의 책을 이득책, 후자의 책을 손해책이라고 하겠습니다.

기본 아이디어는 얻을 수 있는 모든 이득을 취한 뒤, 손해를 감수하면서 어떻게든 완주하는 것입니다.

그렇다면 이득책을 전부 읽은 뒤 손해책을 읽어나가야 합니다.

이득책은 단순히 cost가 적은 순서대로 정렬하면 됩니다. 어차피 책을 읽고 나면 즐거움이 높아져 있으므로 reward 순서는 상관없습니다.

그러나 손해책이 조금 어렵습니다. 손해책은 reward가 가장 큰 순서대로 정렬되어야 합니다. 모든 이득을 다 본 상태이므로 완주가 가능한 책들이라면 그 어떤 손해책이라도 읽을 수 있습니다. 이득책과 다르게 cost 걱정은 없다는 뜻입니다.

잘 이해가 안된다면 거꾸로 생각해봅시다. reward를 소모하면서 cost를 얻는다고 생각하면 이득책과 똑같이 진행될 것입니다. 이 순서를 뒤집어서 진행하면 됩니다. 그러면 reward가 큰 순서대로 정렬하는 것이 정답이 됩니다.

그리디는 발상도 어렵고 증명도 어렵습니다. 그러나 잘 풀리는 날은 발상이 쉽습니다. 그럼에도 증명이 어렵다는 것은 매한가지입니다. 저는 이 문제를 3트만에 성공했지만 풀이를 검증하는 데는 시간이 좀 걸렸습니다. 그리디는 항상 어렵습니다...

코드

import sys
input = sys.stdin.readline
N = int(input())

plus = []
minus = []

for i in range(N):
    x, y = map(int, input().split())
    if (x <= y): plus.append((x, y))
    else: minus.append((x, y))
    

plus.sort(key=lambda x: x[0])
minus.sort(key=lambda x:-x[1])

fun = 0
for i in plus:
    if (fun < i[0]):
        print(0)
        exit(0)
    fun -= i[0]
    fun += i[1]
for i in minus:
    if (fun < i[0]):
        print(0)
        exit(0)
    fun -= i[0]
    fun += i[1]
print(1)