[Kotlin] 백준 27315 : 틀리는 건 싫으니까 쉬운 문제에 올인하려고 합니다

문제 링크

27315번: 틀리는 건 싫으니까 쉬운 문제에 올인하려고 합니다

---

---

문제 해설

기본적으로 틀렸습니다를 최소로 줄이려면 한별이의 아이디어 능력(이하 \(HD\))보다 작거나 같은 아이디어 난이도(이하 \(D\))를 가진 문제 중에서 구현 난이도(이하 \(P\))가 낮은 문제부터 해결해야 한다. 틀렸습니다의 개수는 각 문제마다 \(P\)와 한별이의 구현 능력(이하 \(HP\))의 차이이고, 문제를 풀 때마다 \(HP\)가 1씩 증가하기 때문에 \(P\)가 낮은 문제부터 풀면 \(P\)에 상관없이 풀었을 때 받는 틀렸습니다의 개수보다 더 적어지기 때문이다.

 

그럼 이제 데이터와 에디토리얼의 소유 여부에 대해 생각해봐야 한다. 데이터가 있는 경우에는 틀렸습니다를 받지 않기 때문에 \(P=0\)이라고 생각하면 된다.

 

에디토리얼이 있는 경우에는 \(HD\times 2\geq D\)인 경우에만 에디토리얼을 이해할 수 있고, 이 경우 해당 문제의 \(D\)와 \(P\)는 각각 \(\left \lfloor \frac{D}{2}\right \rfloor\), \(\left \lfloor \frac{P}{2}\right \rfloor\)가 된다고 되어있다. 그런데 사실 한별이가 에디토리얼을 이해하기 위해서는 \(HD\geq \frac{D}{2}\)여야 하고, \(HD\)와 \(D\)가 모두 자연수이기 때문에 실질적으로 에디토리얼이 있는 문제의 \(D\)와 \(P\)는 각각 \(\left \lceil \frac{D}{2}\right \rceil\), \(\left \lfloor \frac{P}{2}\right \rfloor\)이 된다.

 

\(T\)와 \(E\)를 모두 처리했다면 동일하게 \(HD\geq D\)인 문제 중에서 \(P\)가 낮은 순서대로 문제를 풀면 된다. 주의할 점은 틀렸습니다의 총 개수는 Int 범위를 초과할 수 있다는 점, 그리고 에디토리얼이 있는 경우의 \(D\)를 처리할 때 부동소수점 타입을 사용한다면 반올림인 roundToInt()가 아니라 올림인 ceil()를 사용해야 한다는 것이다. 반올림을 사용하게 된다면 부동소수점 타입 특유의 소수부 오차로 인해 xxx.5를 의도하였지만 실제로는 xxx.49999999가 되어 오답이 될 수 있다(이 점을 생각하지 못해 무수한 WA를 받았다 ㅠㅠ).

---

Code

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(' ').map { it.toInt() }
    val problems = PriorityQueue<Problem> { o1, o2 -> if (o1.p == o2.p) o1.d - o2.d else o1.p - o2.p }
    repeat(n) {
        StringTokenizer(readLine()).apply {
            problems.add(Problem(nextToken().toInt(), nextToken().toInt(), nextToken().toInt(), nextToken().toInt()))
        }
    }
    var (hd, hp) = readLine().split(' ').map { it.toInt() }
    var ac = 0L
    var wa = 0L
    val unsolved = PriorityQueue<Problem> { o1, o2 -> if (o1.d == o2.d) o1.p - o2.p else o1.d - o2.d }
    while (problems.isNotEmpty()) {
        val problem = problems.poll()
        if (hd < problem.d) {
            unsolved.add(problem)
            continue
        }

        if (hp < problem.p) wa += problem.p - hp
        if (++ac == m.toLong()) {
            println(wa)
            return@with
        }
        hd++
        hp++
        while (unsolved.isNotEmpty() && unsolved.peek().d <= hd) problems.add(unsolved.poll())
    }
    println(-1)
}

class Problem(d: Int, p: Int, t: Int, e: Int) {
    val d = if (e == 1) d / 2 + d % 2 else d
    val p = if (t == 0) (if (e == 1) p / 2 else p) else 0
}