[BOJ] 19639 - 배틀로얄

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

BOJ - 배틀로얄

문제 유형: 구현, 그리디

문제 난이도: Gold V

시간 제한: 1초

메모리 제한: 1024MB

 

문제

준석이는 총게임을 즐겨 한다. 준석이를 제외한 X명의 플레이어와 함께 게임을 하고 맵에는 Y개의 체력 회복 아이템이 떨어져 있다. 준석이는 처음에 체력을 M만큼 가지고 있다. 준석이는 아주 뛰어난 핵 프로그램을 사용하고 있어서 상대방을 보기만 하면 상대의 실력을 알 수 있고 싸웠을 때 자신의 체력이 어느 만큼 잃게 될지 정확히 맞힐 수 있다. 또 체력 회복 아이템이 어디에 있고 얼마만큼의 체력을 채워주는지 알 수 있다. 준석이가 이동하는 데 걸리는 시간은 무시하고 준석이를 제외한 X명끼리는 싸우지 않는다고 한다.

준석이의 실력이 뛰어나 적과 싸웠을 때 잃게 되는 체력은 M / 2 이하고 체력 회복 아이템 역시 밸런스를 위해 최대 M / 2 만큼 회복할 수 있다. 플레이어의 최대 체력은 M이고 M을 초과하여 회복할 수 없다. 체력이 0 이하로 떨어지면 게임에서 지게 된다.

적들과 체력 아이템이 주어졌을 때 어떤 순서로 적을 죽이고 아이템을 먹어야 하는지 출력해라. 모든 적을 쓰러트리고, 모든 아이템을 다 먹어야 한다.

한번 죽인 적을 다시 죽일 수 없으며, 한번 먹은 아이템을 다시 먹을 수 없다.

 

입력

첫 번째 줄에 X, Y, M (0 ≤ X, Y ≤ 100,000, 2 ≤ M ≤ 100,000)이 주어진다. M은 짝수다.

다음 X개의 줄에는 i번째 사람과 싸웠을 때 잃게 되는 체력이 주어진다. 이 수는 0 이상 M / 2 이하의 정수이다.

다음 Y개의 줄에는 i번째 회복 아이템을 먹었을 때 얻게 되는 체력의 양이 주어진다. 이 수는 0 이상 M / 2 이하의 정수이다.

0 < X + Y가 보장된다.

 

출력

만약 게임에서 이길 방법이 없으면 첫번째 줄에 0을 출력한다.

그렇지 않다면, 수 X + Y개를 다음과 같이 한 줄에 하나씩 출력한다.

• i번째 줄의 수 Vi가 음수라면, i번째 행동에 −Vi번째 적을 죽인다.
• i번째 줄의 수 Vi가 양수라면, i번째 행동에 Vi번째 아이템을 먹는다.

 

풀이

적과 아이템배열을 {값, 인덱스}로 정렬했다.

적은 내림차순, 아이템은 오름차순으로 정리했다.

 

그 후, 순차적으로 읽으며 시뮬레이션하면 된다.

아이템은 작은거부터 먹어야 오버힐 낭비가 적을 것이라 생각해서 였다.

그리고 만약 아이템을 다먹고도 다 잡을 수 없다면, 0을 출력하고 종료하고, 그게 아니라면 매 과정을 정답배열에 담는다.

 

주의할 점은, 모든 적을 잡고 아이템을 다 먹어야 한다는 것이다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int x, y, m;
    cin >> x >> y >> m;
    int limit = m;

    vector<pii> enemies(x);
    vector<pii> items(y);

    for (int i = 0; i < x; i++) {
        int dmg;
        cin >> dmg;
        enemies[i] = {dmg, i + 1};
    }

    for (int i = 0; i < y; i++) {
        int heal;
        cin >> heal;
        items[i] = {heal, i + 1};
    }

    sort(enemies.begin(), enemies.end(), greater<>());
    sort(items.begin(), items.end());

    int j = 0;
    vector<int> ans;
    for (int i = 0; i < x; i++) {
        int dmg = enemies[i].first;
        int idx = enemies[i].second;

        while (j < y && m <= dmg) {
            ans.emplace_back(items[j].second);
            m = min(limit, m + items[j].first);
            j++;
        }
        if (m - dmg <= 0) {
            cout << "0\n";
            return 0;
        }
        m -= dmg;
        ans.emplace_back(-idx);
    }

    while (j < y) {
        ans.emplace_back(items[j].second);
        j++;
    }

    for (const auto &elem : ans) {
        cout << elem << "\n";
    }

    return 0;
}