[백준/C++] 규칙적인 보스돌이 (No. 29792)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 N, M, K가 작고 max값을 이용하면 쉽게 풀 수 있는 문제다.

 

먼저 각 캐릭터가 15분동안 사냥을 할 수 있기 때문에 N개의 캐릭터가 15분 동안 보스를 잡아 얻을 수 있는 메소의 최대값을 구하면 된다.

이후 캐릭터를 M개 선택할 수 있으므로 정렬해서 메소를 얻을 수 있는 캐릭터를 M개 선택하면 된다.

 

이때, 보스를 잡아서 얻을 수 있는 메소를 나타내는 방법은 다음과 같다.

 

먼저 i번째 보스를 잡을 때 타임이 T만큼 걸린다고 가정하고 얻을 수 있는 메소가 D라고 하자.

이후 현재 시간이 S라면 V[S] + D,와 이미 저장되어 있는 V[S+T] 를 비교해서 최대값을 저장해 나가면 된다.

 

즉 이러한 문제는 단계별로 계속해서 최대 메소를 갱신해 나가는 문제로 풀 수 있는 것이다.

 

식으로 요약하면 다음과 같이 나타낼 수 있다.

 

V[S+T] = max(V[S+T], V[S] +D)

 

 

[아이디어 정리]

1. 현재 시간이 i일 때, S의 시간을 써서 보스를 잡아서 얻을 수 있는 돈의 최대값을 갱신해 나간다.
2. 위 방법을 반복해 V[S+T] = max(V[S+T], V[S] +D) 를 갱신해서 얻을 수 있는 최대 메소를 저장한다.
3. 이후 캐릭 별로 얻을 수 있는 최대 메소를 내림차순으로 정렬한다.
4. 정렬 한 다음 메소를 높게 얻는 캐릭터 순서로 M개의 캐릭터를 뽑아 메소를 더해 출력한다.

 

 

Code

 

 

 

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M, K; //M은 캐릭
    cin >> N >> M >> K;
    vector<long long> ca(N);
    for (int i = 0; i < N; i++) {
        cin >> ca[i];
    }
    vector<pair<long long, long long>> boss(K);
    for (int i = 0; i < K; i++) {
        cin >> boss[i].first >> boss[i].second;
    }
    vector<long long> V(901,0);
    vector<long long> maxV(N);
    for (int j = 0; j < N; j++)
    {
        V= vector<long long>(901,0);
        for (int k=0; k<K; k++)
        {
            if (ca[j]==0)
            {
                continue;
            }
            long long sTime = (boss[k].first / ca[j])+ (boss[k].first%ca[j]>0?1:0);
            for (int i=900; i>=0; i--)
            {
                if (i - sTime>=0)
                {
                    V[i] = max({V[i - sTime] + boss[k].second, V[i]});
                }
                else {
                    break;
                }
            }
        }
        maxV[j] = V[900];
    }
    sort(maxV.begin(), maxV.end(), [](long long a, long long b) {
        return a > b; });
    long long ans = 0;
    for (int i = 0; i < min(N,M); i++) {
        ans += maxV[i];
    }
    cout << ans << "\n";
    return 0;
}

---

 

단계 별로 풀어나가면 쉽게 풀 수 있는 문제였다 

 

 

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