[백준 19639번] [그리디] 배틀로얄

일단 풀이방법을 다음과 같이 잡았다.

1.포션은 최대 체력의 절반 이하일때 섭취 (이때, 포션은 최대 절반만큼만 회복가능하므로 최대 HP를 넘어감으로써 손실량은 존재하지 않음)
2.위의 1번 결과에 의하여, 이길 방법이 존재하지 않는 경우는 초기 HP와 포션에 의한 총 회복량의 합이 싸움으로 인해 감소되는 HP보다 작을 때 발생
3.플레이어가 남을 때까지, 해당 플레이어의 공격을 빼고 절반 이하의 HP가 남을 경우 포션을 먹는 행위 반복(만약 포션이 없는 경우는 그대로 진행)

제일 중요한 접근 방법은 최대 절반을 기준으로 현재 HP의 Status를 판단하는 것이다.

포션을 절반보다 더 떨어졌을 때만 섭취하게 되면 Max_hp를 넘어갈 일이 존재하지 않으므로, 초반에 포션에 의한 HP증가량과 싸움에 의한 HP감소량의 힘싸움만 해주면 이길 방법이 존재하지 않는 경우를 걸러낼 수 있다.

 

이를 코드로 구현한 결과는 다음과 같다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int player_num, potion_num, max_hp;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> player_num >> potion_num >> max_hp;
    int half_max_hp = max_hp / 2;
    int current_hp = max_hp;

    vector<pair<int, int> > player_data_store;
    vector<pair<int, int> > potion_data_store;
    // Plyaer한테 총 뺏기는 HP 저장
    long long decrease_value_sum = 0;
    // 포션 먹어서 총 증가하는 HP 저장
    long long increase_value_sum = 0;

    // Player 정보 저장(first: 데이터 값, second : index값)
    for(int i = 0; i < player_num; i++){
        int temp;
        cin >> temp;
        pair<int, int> pair_temp = make_pair(temp, -(i + 1));
        player_data_store.push_back(pair_temp);
        decrease_value_sum += temp;
    }

    // Potion 정보 저장(first: 데이터 값, second : index값)
    for(int i = 0; i < potion_num; i++){
        int temp;
        cin >> temp;
        pair<int, int> pair_temp = make_pair(temp, i + 1);
        potion_data_store.push_back(pair_temp);
        increase_value_sum += temp;
    }

    // 만족하는 케이스가 없는 경우
    // 체력이 절반 이하로 남을 때만 포션을 먹으므로 포션 손실은 발생하지 않는다. (최대 절반까지만 회복할 수 있으므로)
    // 따라서 체력 아이템과 싸울 때 발생하는 체력 손실 사이의 크기를 비교해서 생존가능성을 검토해주면 된다.
    if(max_hp + increase_value_sum <= decrease_value_sum){
        cout << "0\n";
        return 0;
    }

    // 정렬 (오름차순)
    sort(player_data_store.begin(), player_data_store.end());
    sort(potion_data_store.begin(), potion_data_store.end());

    // 결과값 저장하는 vector
    vector<int> result_store;

    // Player가 없어질 때까지 반복
    // Setting
    // 1. player에 해당하는 값만큼 뺸다.
    // 2. 현재 hp가 max_hp의 절반을 넘은 경우 : pass
    //    넘지 않은 경우 : 넘을 때까지 체력아이템 섭취
    //    (만약, 포션이 남지 않은 경우는 그냥 진행)
    while(player_data_store.size()){
        current_hp -= player_data_store.back().first;
        result_store.push_back(player_data_store.back().second);
        player_data_store.pop_back();

        // 뺀 값이 절반을 넘는 상황(포션을 먹어야함)
        if(current_hp <= half_max_hp){
            while(potion_data_store.size()){
                // 포션을 먹어서 hp가 최대 hp의 절반이 넘을 때까지 반복
                // 만약 포션이 없으면 그냥 진행
                current_hp += potion_data_store.back().first;
                result_store.push_back(potion_data_store.back().second);
                potion_data_store.pop_back();

                if(current_hp > half_max_hp) break;
            }
        }   
    }

    // 포션 남은 것 있으면 출력해야할 것에 저장
    while(potion_data_store.size()){
        result_store.push_back(potion_data_store.back().second);
        potion_data_store.pop_back();
    }

    // 결과값 출력
    for(int i = 0; i < result_store.size(); i++){
        cout << result_store[i] << "\n";
    }

    return 0;
}

이 문제는 그리디 알고리즘을 활용한 문제인데

 

이 문제에서 최적 부분 구조(Optimal substructure)는 다음과 같다.

Player와 potion을 오름차순으로 정렬하고, 큰 수부터 검토한다고 하였을 때
각 player로 인한 피해를 회복시키기 위하여 potion의 최소 사용은 존재하는 potion중 회복량이 큰 순서이다.
단, 회복 정도의 기준은 current_hp, 해당 player로 인한 피해, potion에 의한 연산이 최대 HP 절반을 넘는지이다.

이러한 경향성 자체는 전체와 부분 모두 유효하다. 
즉, 각 player와 potion값이 존재하는 것중 최대를 기준으로 해당 행위를 반복하게 되면 탐욕적 선택 속성(Greedy choice property)를 만족하므로 해당 사건은 최적 부분 구조(Optimal substructure)를 만족한다고 볼 수 있다.

단순히 풀기보다는 왜 최적 부분 구조(Optimal substructure)를 만족하는지를 이해하도록 하자.