[C++] 백준 27315번: 틀리는 건 싫으니까 쉬운 문제에 올인하려고 합니다 - Greedy

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

 

24년 2학기 문제해결기법 수업 11주차 B번에 나온 문제와 유사한 문제

다만 데이터가 있는 경우 구현 난이도에 관계 없이 풀 수 있다는 부분만 잘 생각해주면 된다.

 

우선 가장 간단한 생각은 구현 난이도 - HP(구현 능력)의 총합이 작을수록 좋은 결과이므로 구현 난이도에 따른 오름차순 정렬을 하면 좋겠다고 생각했다.

다만 문제는 구현 난이도가 낮지만 아이디어가 높은 경우에는 문제를 해결할 수 없고,

HD는 높지만 구현 난이도가 조금 높은 문제를 여러 문제 해결한 이후 높아진 HD에 따라 구현 난이도가 낮아진 문제를 해결할 수도 있는 가능성이 존재한다.

또한, 데이터가 존재한다면 구현 난이도는 고려할 대상이 아니므로 0점을 부여해도 무방하고,

에디토리얼이 존재한다고 하더라도 HD * 2 > 아이디어 난이도를 성립해야하므로 (아이디어 + 1) / 2 의 아이디어 난이도로 계산해야 한다.

문제를 해결하던 도중 갑자기 11주차 B번 문제가 떠올라서 그대로 적용했더니 문제를 해결할 수 있었다.

 

접근 방법은

1. 아이디어 난이도를 에디토리얼과 데이터의 유무에 따라 계산 후 아이디어 난이도가 낮은 순서대로 정렬한다.

2. 현재의 HD를 마지노선으로 하여 해당 HD보다 작거나 같은 아이디어 난이도를 다른 우선순위 큐(tmp)에 담는데, 이 때에는 구현 난이도가 낮은 순서로 배치한다.

3.  tmp에 존재하는 문제 중 가장 앞에 존재하는 값 (구현 난이도가 가장 낮고, 아이디어는 난이도는 HD보다 작은 값)의 max(구현 난이도 - HP, 0)을 계산하여 ans 변수에 추가한다.

4. 최종적으로 m개의 문제를 계산하기도 전에 tmp에 값이 존재하지 않는다면 아이디어 난이도에 막혀 해결할 수 있는 문제가 없다는 의미이고, m개의 문제를 해결했다면 난이도가 가장 낮으면서 동시에 아이디어 난이도를 만족하는 결과를 출력할 것이다.

 

엄청 어렵다고 생각하진 않지만 해석하고 고려해야 할 부분에 있어 조금 까다롭다고 느꼈고, 실제로 많이 헤맸다.

 

#include <iostream>
#include <queue>
using namespace std;
using ll=long long;
using pll=pair<ll,ll>;
priority_queue<pll, vector<pll>, greater<pll>>q, tmp;
int main(){
    int n, m, c, d; cin >> n >> m;
    long long hd, hp, a, b, ans=0;
    for(int i=0; i<n; i++){
        cin >> a >> b >> c >> d;
        if(c) b=0;
        if(d) q.push({(a+1)/2,b/2});
        else q.push({a,b});
    }
    cin >> hd >> hp;
    while(m){
        while(!q.empty() && q.top().first<=hd){
            tmp.push({q.top().second, q.top().first});
            q.pop();
        }
        if(tmp.empty()) break;
        ans+=max((ll)0, tmp.top().first-hp);
        m--;
        hd++, hp++;
        tmp.pop();
    }
    if(m) ans=-1;
    cout << cnt;
}