[Greedy] 백준 19639번 - 배틀로얄

일단 정답률이 27%라서 쫄았다

 

오늘 하루는 이거겠구나 하는 생각으로 시작한다

 

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

준석 제외 플레이어 수 = X

체력 회복 아이템 수 = Y

준석의 처음 및 최대 체력 = M (짝수)

 

준석이의 체력 잃는 양 <= M/2

 

회복 아이템 회복량 <= M/2

 

내 생각

1. 준석이의 처음 체력의 1/2 이하가 된다면 포션을 먹어준다

   포션은 어차피 M/2보다 작거나 같기 때문에 저 상태에서 먹어주면 M을 넘지 않는다.

 

2. 근데 큰 놈한테 걸려서 엄청 피 봤는데 조그마한 포션 먹으면 어케해?

   -> 큰놈한테 걸려서 체력 1/2이하 되면 큰 포션을 먹어서 1/2이상으로 올려야되나?

      -> 그렇게 먹으나 1/2 초과 될때까지 포션들 집어 먹는 것이나 똑같지 않나?

          -> 그래서 예제에서는 크기 상관없이 1번째(3) 죽이고 2번째(5)죽이고 그랬구나?

    => 1/2 초과될 때까지 포션 먹는 것으로!

 

3. 그렇다면 포션 총 회복량 + M < 적들의 공격으로 인한 체력 마이너스 총량 이면 무조건 준석이가 지는 구조네?

   --> 사실상 적들을 치는 순서가 상관 없다??

 

생각 구현하기

case1)

포션 회복 총량 + M <= 적들 공격 총량 이면 0 return

 

case2)

입력 순서대로 한명씩 대적

M/2 이하가 되면 포션 M/2초과 될 때까지 포션 하나씩 섭취

 

---> 결과 : 시간초과 ㅠ

왜?

알고보니까 내가 endl을 사용했었는데 

endl은 '\n'보다 속도가 느렸다...

그래서 100000개를 출력하다가는 시간 제한 1초를 못 맞추게 되더라....

허무...그자체..

 

그래서 맨 위에 #define endl '\n'을 붙여서 해결해주었다!

 

알고리즘 문제에서는 c++의 endl을 쓰지 말자

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
#define endl '\n'

int X, Y, M;
int input;
long long sum_blood, sum_heal;

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

    cin >> X >> Y >> M;
    int myhp = M;
    int limit = M / 2;
    vector<int> enemy;
    vector<int> potion;

    for (int i = 0; i < X; i++)
    {
        cin >> input;
        sum_blood += input;
        enemy.push_back(input);
    }

    for (int i = 0; i < Y; i++)
    {
        cin >> input;
        sum_heal += input;
        potion.push_back(input);
    }

    int p = 0; //potion 인덱스 
    int e = 0; //enemy 인덱스
    if (sum_blood >= (M + sum_heal)) //이와 같은 조건이면 가차없이 0 반환
    {
        cout << 0 << endl;
        return 0;
    }
    else
    {
        while (X > 0)
        {
            myhp -= enemy[e];
            cout << -(e + 1) << endl; //인덱스에 1더해서 출력
            e++;
            X--;

            while (myhp <= limit && p < Y) //준석의 hp가 M/2이하이면 포션 더해준다
            {
                myhp += potion[p];
                cout << p + 1 << endl;
                p++;
            }
        }
        while (p < Y) //남은 포션 모두 출력
        {
            cout << p + 1 << endl;
            p++;
        }
    }
}