[카드게임(Hard)/G3/Python3, C++]

32143번 카드 게임(Hard ) G3

 

문제
당신은 카드 게임을 하고 있다. 상대의 체력은 H이며, 당신은 다양한 공격력을 가진 카드를 총 N개 가지고 있다. 만약 어떤 카드를 사용하여 공격하면, 상대의 체력은 그 카드의 공격력만큼 줄어든다. 체력이 0 이하가 되면 죽는다. 당신은 패에 있는 카드를 아끼기 위해서 카드를 최대한 적게 써서 상대를 죽이려고 한다. 이때, 다양한 상황에 대비하기 위해서, Q개의 카드에 대하여 각 카드가 순서대로 추가되는 상황에 대해 이 문제를 풀려고 한다. 각 카드가 추가되었을 때 상대를 죽이기 위해 사용해야 하는 카드 개수의 최솟값을 구하거나, 죽이는 것이 불가능한지 판별하여라. 여기서 각 쿼리는 누적되며, 각 카드는 쿼리당 1번만 사용할 수 있다.

입력
첫 번째 줄에 H가 주어진다.두 번째 줄에 N과 Q가 공백으로 구분되어 주어진다. 세 번째 줄에 처음 가지고 있는 카드들의 공격력을 나타내는 N개의 정수 D1,D2,⋯,D_1, D_2, D_N가 공백으로 구분되어 주어진다.네 번째 줄부터 Q개의 줄 중 i번째 줄에 i번째로 추가되는 카드의 공격력을 나타내는 정수 x가 주어진다.

출력
첫 번째 줄에 처음 가지고 있는 N개의 카드에 대해 상대를 죽이기 위해 사용하는 카드 개수의 최솟값을, 만약 죽이는 것이 불가능하다면 −1을 출력하여라.
두 번째 줄부터 Q개의 줄 중 i번째 줄에 i번째 카드를 추가한 후의 문제의 답을 첫 번째 줄과 같은 방법으로 출력하여라.

 

 

자료구조, 그리디 알고리즘, 우선순위 큐

 

현재 가진 카드로 적을 죽일 수 있는 최소의 개수를 구하는 문제이다.

알고리즘을 세우기 위해서  말을 바꾼다면, 만일 적을 충분히 죽일 수 있다면, 어떤 카드를 버려야 하는가?로 볼 수 있다.

 

버려야 하는 카드는 적을 죽이는데 지장이 없는 카드, 즉 가장 공격력이 낮은 카드를 우선적으로 버려야 한다.

Q번마다 카드를 다시 정렬하여 새로 구하는 방식은 무조건 시간초과가 날 것이다.

 

 

적을 죽이는데 필요한 최소한의 카드만 유지하고, 다음 카드를 받았을 때 필요 없어진 카드들을 버리는 방식을 택했다.

 

이를 위해 우선순위 큐 중 최소힙을 사용했고, O(logN) 시간에 가장 작은 카드를 구하였다.

버리더라도 적을 죽일 수 있는지 판단하기 위해 가장 작은 카드의 값을 뺀 값을 미리 비교했다.

Python의 경우 자료형을 알아서 지정해 주지만, C++의 경우 카드들의 총합을 계산할 때 int의 경우 오버플로우가 발생하므로 주의해야 한다.  내가 당했다. 최악의 경우 합이 29억까지도 올라가기 때문이다.

 

import sys
import heapq

hp = int(sys.stdin.readline())
n, q = map(int, sys.stdin.readline().split())
cards = list(map(int, sys.stdin.readline().split()))
sum_c = sum(cards)
heapq.heapify(cards)

while cards and sum_c - cards[0]>= hp:
    sum_c -= heapq.heappop(cards)
print(len(cards) if sum_c>=hp else -1)

for _ in range(q):
    add_c = int(sys.stdin.readline())
    sum_c += add_c
    heapq.heappush(cards, add_c)
    
    while cards and sum_c - cards[0]>= hp:
        sum_c -= heapq.heappop(cards)
    print(len(cards) if sum_c>=hp else -1)

 

 

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

priority_queue<int, vector<int>, greater<int>> hq;
int health, n, q, card;
long total_cards = 0;

void solution()
{
    while(total_cards - hq.top() >= health)
    {
        total_cards -= hq.top();
        hq.pop();
    }
    cout<<(total_cards < health ? -1 : (int)hq.size())<<"\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
    cin>>health>>n>>q;
    while (n--)
    {
        cin>>card;
        total_cards += card;
        hq.push(card);
    }
    solution();
    while(q--)
    {
        cin>>card;
        total_cards += card;
        hq.push(card);
        solution();
    }
}

 

---

 

문제의 아이디어도 재밌었고, 같은 대회 문제인 카드 게임(Easy)와 반대로 구하는 문제이다 보니 발상의 전환이 쉽지 않았던 문제이다. 

Solved.ac 기여도 했던 추천하는 문제 중 하나이다.