[백준] 당근 훔쳐 먹기 18234번 (c++)

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

 

풀이 방법

pi는 wi보다 항상 크다.라는 조건에 의해 그리디로 풀이할 수 있음을 파악했다.

pi는 당근을 뽑지 않으면 계속해서 누적되다가 해당 당근을 뽑게 된다면 누적된 pi와 wi만큼 맛을 얻을 수 있다.

이를 통해 T일 전까지 가장 큰 pi를 계속 누적을 하다 마지막에 뽑는 것이 가장 많은 맛을 얻을 수 있다는 것을 알 수 있다.

 

또한 pi는 wi보다 항상 크다라는 조건에 의해, 만약 T가 6이고 당근이 3종류라면 6, 5, 4일 차에만 당근을 뽑아 먹고, 1, 2, 3일 차에는 당근을 안 뽑아 먹는 것이 더 크다는 조건을 알 수 있다.

 

(만약 뽑게 된다면, wi가 중간에 포함되어야 하기 때문에 안 뽑고 Pi만큼 얻는게 더 좋다.)

 

이렇게 풀이하기 위해 당근을 pi가 큰게 먼저 나오도록 정렬을 했다.

pi가 같다면 wi가 큰 것이 유리하기 때문에 wi가 큰 게 오도록 정렬

 

 

실수한 부분 정렬 함수를 아래와 같이 만들어야 잘 동작을 한다.

 

bool cmp(const pair<int, int>& p1, const pair<int, int>& p2) {
    if (p1.second != p2.second) return p1.second > p2.second;  // 내림차순 정렬
    return p1.first > p2.first; // second가 같으면 first 기준 내림차순
}

 

아래와 같이 작성하게 된다면 p1.first == p2.first , p1.second == p2.second일 경우 에러가 발생한다.

bool cmp(const pair<int, int>& p1, const pair<int, int>& p2) {
	if (p1.first < p2.first) return false;
    else if (p1.first == p2.first) {
    	if (p1.second < p2.second) return false;
        else return true;
    }
    else return true;
}

 

전체 코드

#include<iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, t;
vector<pair<int, int> > wp;


int w[200001];
int p[200001];

bool cmp(const pair<int, int>& p1, const pair<int, int>& p2) {
    if (p1.second != p2.second) return p1.second > p2.second;  // 내림차순 정렬
    return p1.first > p2.first; // second가 같으면 first 기준 내림차순
}

int main() {

    cin >> n >> t;

    int a, b;
    for (int i = 0;i < n;i++) {
        cin >> a >> b;
        wp.push_back(make_pair(a, b));
    }

    sort(wp.begin(), wp.end(), cmp);

    long long ans = 0;
    int idx = min(t, n);
    for (int i = 0;i < idx;i++) {
        ans += (wp[i].first + wp[i].second * static_cast<long long>(t - i - 1));
    }
    cout << ans << endl;
    return 0;
}