[BOJ/백준][Gold3] 18234 : 당근 훔쳐 먹기 (C++)

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

18234번: 당근 훔쳐 먹기

 

 

[난이도] Gold3
[유형] Greedy

[풀이]
pi가 항상 wi보다 크기 때문에 어떤 당근 i를 마지막 한번만 뽑아 먹는 것이 이득입니다.
중간에 뽑아서 다시 심게 되면 영양분이 p만큼 증가해야 되는 날에 다시 심게 되면서 w만 증가하게 되기 때문입니다.
결국 모든 당근을 한번씩만 뽑아먹어야 한다면, p가 클 수록 나중에 뽑아 먹는 것이 이득입니다.
p가 같다면 w가 큰 것을 선택해야 합니다.

정렬을 이용해 큰 (p,w) 부터 뽑으면서 계산한 뒤 정답에 더해주면 됩니다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,T;
vector<pair<int,int>> v;
int main(){
    scanf("%d%d",&N,&T);
    for(int i=0;i<N;i++) {
        int w,p;
        scanf("%d%d",&w,&p);
        v.push_back({p,w});
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());

    long long ans=0;
    for(int i=0;i<N;i++){
        auto [p,w] = v[i];
            ans+=w+(long long)p*(T-i-1);
    }
    printf("%lld",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/18234.cpp