[BOJ/Gold 5] 백준 29792 규칙적인 보스돌이(C++)

문제 링크

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

29792번: 규칙적인 보스돌이

 

문제

카오는 오랫동안 메이플스토리를 플레이하며 N개의 캐릭터를 육성하였다.

지속적인 스펙업을 위해 꾸준하게 메소를 벌어야 할 필요성을 느낀 카오는, 지금까지 키워온 캐릭터들을 활용하여 메소를 벌기로 하였다. 여러 캐릭터로 보스를 효율적으로 잡기 위해, 하루에 한 캐릭터 당 최대 15분씩, 최대 M개의 캐릭터만 보스를 잡기로 하였다.

캐릭터가 보스에게 데미지를 넣으면 보스의 체력이 데미지만큼 감소하며, 보스의 체력이 0 이하가 되면 보스를 잡게 된다. 데미지의 계산은 매초 이루어지기 때문에, 1초 미만의 시간 동안 적용된 데미지는 보스에게 적용되지 않는다.

캐릭터마다 주어진 15분 동안은 매초 일정한 데미지를 넣을 수 있으며, 보스를 잡은 후 다른 보스를 잡으러 떠나는 시간은 계산하지 않는다. 캐릭터마다 각 보스는 1회씩만 처치할 수 있으며, 다른 캐릭터가 잡은 보스라도, 현재 캐릭터가 잡지 않은 보스라면 잡을 수 있다. 보스를 잡던 도중 캐릭터를 변경하는 것은 불가능하며, 캐릭터가 상대하는 보스의 체력은 공유되지 않아, 오롯이 한 캐릭터의 힘으로 보스를 상대해야 한다.

보스 몬스터의 체력, 보상 메소 정보와 캐릭터의 데미지 정보가 주어질 때, 카오가 계획에 맞추어 하루에 보스를 잡아 얻을 수 있는 최대 메소를 구해보자.

 

입력

첫 줄에는 보유한 캐릭터의 개수 N, 하루에 사용할 캐릭터의 개수 M, 보스의 가짓수 K가 공백으로 구분되어 주어진다. (1 ≤ M ≤ N ≤ 49; 1 ≤ K ≤ 13)

그다음 N줄에 걸쳐서 캐릭터가 1초에 가하는 데미지 D가 주어진다. (1 ≤ D ≤ 10^11)

그다음 K줄에 걸쳐서 보스의 체력 P와 보스를 처치했을 때 드랍하는 메소 Q가 공백으로 구분되어 주어진다. (1 ≤ P ≤ 2.66 × 10^11; 1 ≤ D ≤ 1,596,506)

입력으로 들어오는 모든 수는 정수임이 보장된다.

 

출력

카오가 계획에 맞추어 보스를 잡았을 때, 하루에 보스를 잡아 얻을 수 있는 최대 메소를 출력한다.

 

예제 입력 1

3 2 3
1
2
3
900 30
1800 40
2700 50

예제 출력 1

110

다음 경우에 110메소를 획득할 수 있다.

•  2번째 캐릭터로 15분에 걸쳐 2번째 보스를 잡아 40메소 획득
•  3번째 캐릭터로 5분에 걸쳐 1번째 보스를 잡아 30메소 획득
•  3번째 캐릭터로 10분에 걸쳐 2번째 보스를 잡아 40메소 획득

 

예제 입력 2

2 2 3
10
20
8999 10
17999 100
1 1

예제 출력 2

110

 

다음 경우에 110메소를 획득할 수 있다.

•  1번째 캐릭터로 15분에 걸쳐 1번째 보스를 잡아 10메소 획득
•  2번째 캐릭터로 15분에 걸쳐 2번째 보스를 잡아 100메소 획득

 1번째 캐릭터가 14분 59초 동안 넣을 수 있는 데미지는 8,990이다. 남은 시간 1초 동안 1번째 보스와 3번째 보스를 모두 잡을 수 없어, 위와 같은 결과가 나오게 된다.

 

노트

보스의 체력 P의 제한 2.66 × 10^11와 드랍하는 메소 Q의 제한 1,596,506은 2023년 8월 10일 업데이트 이전의 가장 많은 체력(카오스 혼테일)과 결정의 가격(노멀 파풀라투스)을 가진 일간 보스의 정보이다.

 

알고리즘 분류

• 배낭 문제

 

풀이

캐릭터마다 최대 900초(=15분)동안 얼마나 많은 메소를 벌었는지를 판단하기 위해, N번째 캐릭터가 S초까지 벌어들인 메소를 기록하는 DP[N][901]이라는 2차원 배열을 선언한다.

그리고 첫 번째 캐릭터부터 N번째 캐릭터까지, 각 캐릭터가 K번째 보스를 잡고 S초가 경과했을 때 벌어들일 수 있는 메소 수치의 최댓값을 기록한다.

K번째 보스를 잡고 몇 초가 경과했는지를 판단하기 위해 보스의 체력 P를 현재 캐릭터가 1초에 보스에게 줄 수 있는 대미지 D[N]으로 나누고 그 몫을 구한다. 나머지가 0이라면 몫이 K번째 보스를 잡을 때 걸리는 시간이며, 나머지가 0이 아니라면 몫 + 1이 보스를 잡을 때 걸리는 시간이다.

마지막으로, N명의 캐릭터 각각 최대로 벌어들일 수 있는 메소를 구해 우선순위 큐에 push한다. 그리고 우선순위 큐에서 M개의 메소 수치를 pop하면서 Answer 변수에 더한다. 그럼 Answer 변수의 값이 문제에서 요구하는 M명의 캐릭터가 벌어들일 수 있는 메소의 최대 수치가 된다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX_N 50
#define MAX_S 901
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct BOSS {
    LL P, Q;
};

LL N, M, K, P, Q;
LL D[MAX_N];
vector<BOSS> Boss;
LL DP[MAX_N][MAX_S];
priority_queue<LL> PQ;
LL Answer;

void input() {
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        cin >> D[i];
    }
    for (int i = 0; i < K; i++) {
        cin >> P >> Q;
        Boss.push_back({ P,Q });
    }
}

void settings() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < K; j++) {
            LL Hunt = (Boss[j].P / D[i]);
            if (Boss[j].P % D[i] > 0) {
                Hunt++;
            }
            for (int k = (MAX_S - 1); k >= 0; k--) {
                if (k - Hunt >= 0) {
                    DP[i][k] = max(DP[i][k], DP[i][k - Hunt] + Boss[j].Q);
                }
            }
        }
    }
    for (int i = 0; i < N; i++) {
        LL Meso = 0;
        for (int j = 0; j < MAX_S; j++) {
            Meso = max(Meso, DP[i][j]);
        }
        PQ.push(Meso);
    }
    while (M--) {
        Answer += PQ.top();
        PQ.pop();
    };
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}