BOJ 17221 - 인재야 머쉬맘 잡았어? 링크
(2024.04.12 기준 P3)

문제

인재는 체력 $A$, 공격력 $B$를, 머쉬맘은 체력 $X$, 공격력 $Y$를 가지고 있다.
인재의 선공으로, 서로 번갈아가며 한 턴에 한 번의 행동을 할 수 있다.
행동에는 다음의 세 가지 패턴만 존재한다.

• 공격: 현재 공격력 만큼의 피해를 입힌다.
• 반격: 이번 턴에 피해를 받지 않고, 상대방의 공격력만큼의 피해를 입힌다. 체력이 현재 체력에서 $10\%$ 증가한다. 소수점은 버린다.
• 버프: 공격력을 현재 공격력에서 $20\%$ 올리고, 이번 턴에만 받는 피해가 세 배가 된다. 소수점은 버린다.

머쉬맘은 공격만 가능하다. $A$, $B$, $X$, $Y$가 주어질 때, 가장 빠르게 머쉬맘을 사냥할 때의 필요한 행동의 수 출력

알고리즘

그리디적으로 행동의 순서를 정하고, 각 행동을 몇 번 해야하는지는 브루트포스로 찾기. 또한, 최적화를 위해 적당한 커팅

풀이

공격을 선택하면 $A = A-Y$, $X = X-B$.
반격을 선택하면 $A = \lfloor 1.1A \rfloor$, $X = X-Y$.
버프를 선택하면 $A = A - 3Y$, $B = \lfloor 1.2B \rfloor$.

• 공격, 반격의 우선순위
  공격 $\rightarrow$ 반격이 가능하다고 생각해보자.
  여기서 공격 $\rightarrow$ 반격 대신 반격 $\rightarrow$ 공격을 해도 동일한 결과를 가져온다.
  
  하지만 반격 $\rightarrow$ 공격이 가능하다고 생각해보자.
  여기서 반격 $\rightarrow$ 공격 대신 공격 $\rightarrow$ 반격을 무조건 할 수 있지 않다.
  만약에 현재 인재의 체력이 머쉬맘의 공격력보다 같거나 낮다면, 순서를 바꿀 수 없게 된다.
  
  그러므로 항상 공격보다 반격이 앞서야 한다.

• 공격, 버프의 우선순위
  만약 인재의 체력이 머쉬맘의 공격을 충분히 버틸 수 있다고 생각해보자.
  
  1. 버프를 $i$번 쓰고 공격을 할 때
  2. 버프 $j(j<i)$번을 쓰고 공격을 하고 버프 $i-j$번을 쓰고 공격을 할 때
  
  버프는 공격력을 일정 비율로 올릴 수 있다. 그러므로 버프를 $i$번 사용할 수 있다면 $i$번을 사용하고 공격하는 것이 당연히 이득이다. 그래서 1번이 2번보다 횟수가 같거나 적음을 알 수 있다.
  
  그러므로 항상 공격보다 버프가 앞서야 한다.

• 반격, 버프의 우선순위
  버프 $\rightarrow$ 반격이 가능하다고 생각해보자.
  여기서 버프 $\rightarrow$ 반격 대신 반격 $\rightarrow$ 버프를 해도 동일한 결과를 가져온다.
  
  하지만 반격 $\rightarrow$ 버프가 가능하다고 생각해보자.
  여기서 반격 $\rightarrow$ 버프 대신 버프 $\rightarrow$ 반격을 무조건 할 수 있지 않다.
  만약에 현재 인재의 체력이 머쉬맘의 공격력의 $3$배보다 같거나 낮다면, 순서를 바꿀 수 없게 된다.
  
  그러므로 항상 버프보다 반격이 앞서야 한다.

위에서 도출한 우선순위를 합치면, 반격 $\rightarrow$ 버프 $\rightarrow$ 공격 순이 최적이다.
그럼 이제 $i+j+k$ (반격 $i$번 $\rightarrow$ 버프 $j$번 $\rightarrow$ 공격 $k$번)의 최솟값을 모든 $i$와 $j$에 대해서 찾으면 된다.

그런데 문제점이 있다. 체력이나 공격력이 쓸데없이 너무 높아지는 경우가 생긴다. 여기서 생각을 해보자. 체력이나 공격력이 너무 높아진 상태에서 더이상 체력이나 공격력을 올릴 필요가 있을까? 전혀 필요가 없어진다. 그러므로 체력이나 공격력이 적당히 높아지면 early cut을 할 필요가 있다.

반격으로만 머쉬맘을 사냥할 수 있어서, 반격은 필수로 확인해야 한다. 하지만 버프로 공격력이 오르지 않는다면 버프라는 행동은 전혀 쓸모가 없다.
그래서 $B < 5$일 땐, $i$만 고려해서 답을 구하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e8;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int A, B, X, Y; cin >> A >> B >> X >> Y;

    // 반격 -> 버프 -> 공격
    // 반격으로만 머쉬맘을 사냥할 수 있어서, 반격은 필수로 확인해야 하지만
    // 버프는 공격력이 오르지 않는다면 전혀 쓸모가 없다.

    // 버프로 공격력이 오르지 않는 범위
    if (B < 5){
        int ans = ceil((float)X / Y); // 반격으로만 머쉬맘 사냥했을 때의 행동의 수

        // i: 반격 횟수
        // 머쉬맘이 살아 있어야 한다.
        for (int i = 0, res1, res2; X > 0; i++){
            res1 = ceil((float)X / B); // 인재가 공격해야 하는 횟수
            res2 = ceil((float)A / Y); // 머쉬맘이 공격해야 하는 횟수
            // 인재가 선공이기 때문에, 인재의 공격 횟수가 머쉬맘보다 같거나 적어야 한다.
            if (res1 <= res2) ans = min(ans, i + res1);
    
            // 반격 1회가 추가된다.
            X -= Y;
            A = A * 11 / 10;
    
            // 체력이 너무 커지면 더이상 반격으로 체력을 올리는 의미가 없어진다.
            if (A > inf) break;
        }

        cout << ans;
    }

    // 버프로 공격력이 오를 수 있다.
    else{
        int ans = ceil((float)X / Y); // 반격으로만 머쉬맘 사냥했을 때의 행동의 수

        // i: 반격 횟수
        // 머쉬맘이 살아 있어야 한다.
        for (int i = 0, a, b, x, y; X > 0; i++){

            // 버프에 따른 수치를 조정해야 하기 때문에 변수를 따로 저장해 놓는다.
            a = A; b = B; x = X; y = Y;

            // j: 버프 횟수
            // 인재가 살아 있어야 한다.
            for (int j = 0, res1, res2; a > 0; j++){
                res1 = ceil((float)x / b); // 인재가 공격해야 하는 횟수
                res2 = ceil((float)a / y); // 머쉬맘이 공격해야 하는 횟수
                // 인재가 선공이기 때문에, 인재의 공격 횟수가 머쉬맘보다 같거나 적어야 한다.
                if (res1 <= res2) ans = min(ans, i + j + res1);

                // 버프 1회가 추가된다.
                a -= y * 3;
                b = b * 6 / 5;

                // 공격력이 너무 커지면 더이상 버프로 공격력을 올리는 의미가 없어진다.
                if (b > inf) break;
            }

            // 반격 1회가 추가된다.
            X -= Y;
            A = A * 11 / 10;

            // 체력이 너무 커지면 더이상 반격으로 체력을 올리는 의미가 없어진다.
            if (A > inf) break;
        }

        cout << ans;
    }
}

• Python

import sys; input = sys.stdin.readline
from math import ceil
inf = 1e8

A, B, X, Y = map(int, input().split())

# 반격 -> 버프 -> 공격
# 반격으로만 머쉬맘을 사냥할 수 있어서, 반격은 필수로 확인해야 하지만
# 버프는 공격력이 오르지 않는다면 전혀 쓸모가 없다.

# 버프로 공격력이 오르지 않는 범위
if B < 5:
    ans = ceil(X / Y) # 반격으로만 머쉬맘 사냥했을 때의 행동의 수

    i = 0 # 반격 횟수
    while X > 0: # 머쉬맘이 살아 있어야 한다.
        res1 = ceil(X / B) # 인재가 공격해야 하는 횟수
        res2 = ceil(A / Y) # 머쉬맘이 공격해야 하는 횟수
        # 인재가 선공이기 때문에, 인재의 공격 횟수가 머쉬맘보다 같거나 적어야 한다.
        if res1 <= res2:
            ans = min(ans, i + res1)

        # 반격 1회가 추가된다.
        i += 1
        X -= Y
        A = int(A * 1.1)

        # 체력이 너무 커지면 더이상 반격으로 체력을 올리는 의미가 없어진다.
        if A > inf:
            break

    print(ans)

# 버프로 공격력이 오를 수 있다.
else:
    ans = ceil(X / Y) # 반격으로만 머쉬맘 사냥했을 때의 행동의 수

    i = 0 # 반격 횟수
    while X > 0: # 머쉬맘이 살아 있어야 한다.

        # 버프에 따른 수치를 조정해야 하기 때문에 변수를 따로 저장해 놓는다.
        a, b, x, y = A, B, X, Y

        j = 0 # 버프 횟수
        while a > 0: # 인재가 살아 있어야 한다.
            res1 = ceil(x / b) # 인재가 공격해야 하는 횟수
            res2 = ceil(a / y) # 머쉬맘이 공격해야 하는 횟수
            # 인재가 선공이기 때문에, 인재의 공격 횟수가 머쉬맘보다 같거나 적어야 한다.
            if res1 <= res2:
                ans = min(ans, i + j + res1)

            # 버프 1회가 추가된다.
            j += 1
            a -= y * 3
            b = int(b * 1.2)

            # 공격력이 너무 커지면 더이상 버프로 공격력을 올리는 의미가 없어진다.
            if b > inf:
                break

        # 반격 1회가 추가된다.
        i += 1
        X -= Y
        A = int(A * 1.1)

        # 체력이 너무 커지면 더이상 반격으로 체력을 올리는 의미가 없어진다.
        if A > inf:
            break

    print(ans)