[C++][백준 22941] RPG 마스터 오명진

문제

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

접근 방법

HP와 ATK의 범위를 보면 ATK가 1이고 HP가 2^31-1일 시 시뮬레이션으로 해결하기는 힘들다는 것을 알 수 있습니다.
그렇기에 계산을 통해 용사가 이길 수 있는지 구해내야 합니다.

코드

#include <iostream>
using namespace std;

using ll = long long;

struct Stats
{
    ll hp, atk;

    void input()
    {
        cin >> hp >> atk;
    }
};

Stats hero, enemy;
ll P, S;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    hero.input();
    enemy.input();
    cin >> P >> S;

    ll heroAttackCnt = (enemy.hp + hero.atk - 1) / hero.atk;
    ll enemyRemainHP = enemy.hp - hero.atk * (heroAttackCnt - 1);
    if (enemyRemainHP >= 1 && enemyRemainHP <= P)
    {
        heroAttackCnt = (enemy.hp + S + hero.atk - 1) / hero.atk;
    }

    cout << (hero.hp - enemy.atk * (heroAttackCnt - 1) > 0 ? "Victory!" : "gg");

    return 0;
}

풀이

용사가 선공이라는 점에서 상대의 체력을 0이하로 만들기 위해 때려야 하는 횟수가 동일하면 용사가 이깁니다.
그렇기에 용사가 마왕을 때려야 하는 횟수를 구한 뒤 그 횟수에 -1한 만큼을 용사가 맞았을 때 살아있으면 이길 수 있는 것입니다.
마왕의 경우 죽기 직전까지 맞았을 때 P이하이고 1이상인 상태로 살아있다면 S만큼 회복할 수 있다는 점을 고려해 주면 됩니다.