BOJ 12430 - 생존자

문제 링크 : https://www.acmicpc.net/problem/12430

문제 풀이

  문제를 딱 읽으면 DP향이 느껴진다. 냅색 혹은 동전으로 낼 수 있는 가격과 비슷한 느낌이지만, 정확히 허기질 때만 다른 음식을 먹을 수 있다. A[x]를 x일 동안 버틸 수 있는 지를 체크하는 것이라면 i번째 음식은 0~$P_i$ 값을 $S_i ~ P_i + S_i$에 더하는 즉, 업데이트를 하는 효과를 가지고 있다. 

하지만 동전 문제와 다른 점은 한계인 $P_i$가 존재하기 때문에 업데이트하는 순서에 따라서 나오는 결과값이 달라질 것이다. 업데이트 한다는 것은 그 음식을 먹는 가능성을 주는 것이기 때문에 정답 결과가 나오는 경우 때, 음식을 먹는 순서대로 업데이트를 실시한다면 최댓값을 얻어낼 수 있다. 

 그렇다면 최대한 오래 살기 위해서 음식을 어떻게 먹어야 할까? a->b 순서가 b->a 순서 보다 무조건 유리한 조건을 찾으면 된다. a번 음식의 업데이트로 위치가 $S_a$ 만큼 더해지는데, 이 위치가 $P_b$ 이하면 한 번 더 업데이트 할 수 있다. 반대의 경우도 마찬가지이다. 천천히 놓고 생각을 해본다면 $P_a - S_b < P_b - S_a$ 인 경우에 a를 먼저 먹는 것이 무조건 옳다고 할 수 있다. 이를 식 정리를 한다면 $S_a + P_a < S_b - P_b$ 인 경우에 a를 먼저 먹는 것이고, 즉, S+P 에 대해서 정렬을 하면 되는 것이다. 단 2개만 아닌 N개 모두 정렬해도 되는 이유는 exchange arguments의 힘을 빌리면 알 수 있다. 

 시간 복잡도는 O(NP)가 되어서 아슬아슬하다고 느낄 수 있으나, 10초의 제한 시간을 보고 오히려 이 풀이가 맞다는 확신을 가질 수 있다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
 
#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
//cout<<fixed;
//cout.precision(12);
 
struct poi{
    ll val,xx,yy;
};
 
vector<ll> x;
ll n,m;
ll mod=998244353;
string s;
pii arr[1010101];
ll dp[1010101];
 
bool sf(pii a,pii b){
    return a.ff+a.ss<b.ff+b.ss;
}
priority_queue<ll,vector<ll>,greater<ll>> pq;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t,T;
    cin>>T;
    dp[0]=1;
    for(t=1;t<=T;t++){
        ll i,j,k,l;
        ll ans=0;
        cin>>n;
        for(i=1;i<=210100;i++)
            dp[i]=0;
 
        for(i=1;i<=n;i++)
            cin>>arr[i].ff>>arr[i].ss;
        sort(arr+1,arr+1+n,sf);
        for(i=1;i<=n;i++){
            for(j=arr[i].ff;j>=0;j--){
                if(dp[j]){
                    //cout<<i<<' '<<j<<' '<<j+arr[i].ss<<'\n';
                    ans=max(j+arr[i].ss,ans);
                    dp[j+arr[i].ss]++;
                }
            }
        }
 
        cout<<"Case #"<<t<<": "<<ans<<'\n';
    }
}