(C++) - 백준(BOJ) 18234번 : 당근 훔쳐 먹기

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

18234번: 당근 훔쳐 먹기

greedy 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

* 먹은 당근의 합을 구하는 과정에서 21억을 초과할 수 있으므로 long long으로 변수를 선언해줍니다.

n만큼 w,p를 입력받아야하므로 vector pair long long 형태로 변수 carrot을 선언해줍니다.

📔 풀이과정

 키워서 먹는다라는 말이 있습니다. 그 말은 p가 크면 클 수록 나중에 먹는 것이 이득이라는 말입니다. 1. p에 대한 오름차순, p가 같다면 w에 대한 오름차순으로 정렬해줍니다. 2. i일 후에 얻을 수 있는 맛의 합은 w + p * (i + t - n)이 됩니다. 3. n일 동안에 해당 합을 ans에 저장합니다

 

📔 정답출력

ans를 출력합니다.

---

📕 Code

//당근 훔쳐 먹기
#include <bits/stdc++.h>
#define ll long long
using namespace std;
using pll = pair<ll,ll>;
ll n, t, ans;
vector <pll> carrot;

int main(){
    cin >> n >> t;
    carrot.resize(n);
    for(int i = 0,w,p; i < n; i++){
        cin >> w >> p;
        carrot[i] = {p,w};
    }
    sort(carrot.begin(),carrot.end());

    for(int i = 0; i < n; i++){
        ll w = carrot[i].second;
        ll p = carrot[i].first;
        ans += w + p * (i + t - n);
    }
    cout << ans;
}