[C++] 백준 28448번: 광기의 PS - Greedy

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

 

문제 N개 / 난이도 K / 시간 T 가 주어진다.

한 문제를 풀 때마다 광기는 K * T 만큼 쌓이고, 최대 광기는 L 만큼만 쌓여야 한다.

만약 문제를 해결하면 광기는 min(KT, 5K) 만큼 사라지게 된다.

 

여기서 우선 알 수 있는 사실은 만약 T <= 5라면 광기는 0과 마찬가지인 셈이 된다.

즉, T <= 5 인 경우는 고려할 대상이 아니므로 그냥 해결 시간에 더해주면 된다.

 

문제는 T > 5 인 경우이다. 해당 경우에는 광기가 누적되게 된다.

만약 L - 현재 광기 < Ki * Ti 라면 광기는 L보다 커지므로 휴식을 취해야 한다.

여기서 휴식을 가장 적게 취하면서 모든 문제를 해결할 방법을 구해야 한다.

 

우선 누적이 되는 광기의 양을 식으로 표현하면

K * (T - 5)라고 볼 수 있다.

 

그래서 처음 들었던 생각은 K*T가 작은 순서대로 정렬을 해야하나 싶었다.

어차피 K*T + 현재 광기 > L 인 경우에는 T의 값에 상관 없이 휴식을 취해야 하는데,

K*T + 현재 광기 > L 만큼 휴식을 취해야 하므로 단순히 K*T가 작으면 되지 않을까 생각했다.

 

그런데 다시 생각해보니 T의 값은 반드시 5보다 큰 값만을 고려하므로 T의 값에는 상관 없이 사라지는 광기의 양은 5K로 고정이다.

그러므로 K*T가 작다고 하더라도 사라지는 광기의 양도 똑같이 작은 값이면 greedy하지 않은 경우가 발생할 수 있을 것이라 생각했다.

그래서 K*T에도 영향을 미치고 사라지는 광기의 양에도 영향을 미치는 값인 K에 대해 정렬을 하고자 생각했다.

 

우선 K가 작은 순서대로 정렬을 구상해봤다.

그러면 K*T 값 + 현재 광기가 L보다 작을 확률은 올라가겠지만, 사라지는 광기의 양이 적으므로 어차피 L보다 커지는 값이라면 그만큼 휴식을 취하는 시간도 늘어날 것이라고 생각했다.

 

이를 좀 더 구체화했다.

만약 다음 Ki*Ti를 X라고 한다면

자명한 사실은 (현재 광기 + X) > L 이라면 휴식을 취해야 한다.

그런데 여기서 X가 작을수록 휴식을 취해야하는 시간이 줄어들고, 그 중 K가 클수록 사라지는 광기의 양이 증가한다.

그러므로 K가 큰 값부터 내림차순으로 정렬을 수행했다.

 

시간 T에 대해서도 고려해야하나 생각했는데,

사라지는 광기의 양은 T에 대해 무관하므로 어차피 K가 동일하다면 T는 상관없이 사라지는 광기의 양이 일치하게 되므로 굳이 고려할 대상이 아니라고 판단했다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll=long long;
ll ans, cnt;
vector<pair<ll, ll>>v;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll n, l, x, y; cin >> n >> l;
    for(int i=0; i<n; i++){
        cin >> x >> y;
        if(y<=5) ans+=y;
        else v.push_back({x,y});
    }
    sort(v.rbegin(), v.rend());
    for(auto& e: v){
        ans+=e.second;
        cnt+=e.first*e.second;
        if(cnt>l){
            ans+=cnt-l;
            cnt=l;
        }
        cnt-=5*e.first;
    }
    cout << ans;
}