[Kotlin] 백준 22941 : RPG 마스터 오명진

문제 링크 : https://www.acmicpc.net/problem/22941

---

문제 해설

주어진 조건에 따라 용사의 승리 여부를 시뮬레이션해야 합니다.

 

다만 시간 제한이 0.3초밖에 안되고 공격력은 최소가 \(1\)인 반면 HP는 최대 \(2^{31}-1\)이기 때문에 최악의 경우라면 \((2^{31} - 1)\times 2\)번의 연산을 수행해야 해서 시간 초과가 발생합니다.

 

하지만 문제에서 요구하는 답을 구하려면 용사가 쓰러지기 전에 마왕이 먼저 쓰러지는지의 여부만 확인하면 되기 때문에 단순 수학 계산만으로도 판별할 수 있습니다.

 

우선 마왕을 쓰러트리기 위해 필요한 용사의 공격 횟수를 구해서 소수점 이하는 올림처리 해줍니다.

braveAttackCount = (devilHp + braveAtk - 1) / braveAtk

그런데 마왕은 HP가 1 ~ \(P\) 사이일 때 HP를 \(S\)만큼 회복하는 스킬이 있습니다. 위에서 구한 용사의 공격 횟수는 마왕의 스킬을 생각하지 않고 계산한 값이기 때문에 다시 계산을 해줘야 합니다.

 

마왕의 스킬 사용 여부는 용사가 마지막 공격을 하기 직전에 남은 마왕의 HP를 통해 알 수 있습니다. 즉, 마왕의 HP \(\times\) (용사의 필요 공격 횟수 - 1)의 값이 1 ~ \(P\) 사이라면 마왕의 HP + \(S\)를 기준으로 용사의 필요 공격 횟수를 다시 계산하면 마왕의 스킬 사용 여부까지 감안한 공격 횟수를 계산할 수 있습니다.

if (devilHp - braveAtk * (braveAttackCount - 1) in 1..p) {
    braveAttackCount = (devilHp + s + braveAtk - 1) / braveAtk
}

이제 용사가 쓰러지기 전에 마왕을 쓰러트릴 수 있는지만 판별하면 됩니다.

 

용사가 먼저 공격하고 그 다음 마왕이 공격하기 때문에 마왕이 쓰러지기 직전까지, 다시 말해 마왕이 (용사의 필요 공격 횟수 - 1) 만큼 용사를 공격했을 때 용사의 HP가 남아있는지 판별하면 용사가 승리했는지 확인할 수 있습니다.

Code

fun main() = with(System.`in`.bufferedReader()) {
    val (braveHp, braveAtk, devilHp, devilAtk) = readLine().split(' ').map { it.toLong() }
    val (p, s) = readLine().split(' ').map { it.toLong() }
    var braveAttackCount = (devilHp + braveAtk - 1) / braveAtk
    if (devilHp - braveAtk * (braveAttackCount - 1) in 1..p) {
        braveAttackCount = (devilHp + s + braveAtk - 1) / braveAtk
    }
    println(if (braveHp - devilAtk * (braveAttackCount - 1) > 0) "Victory!" else "gg")
}