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

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

 

 

이 문제는 N개 종류의 당근이 존재하고 각 당근의 종류별로 초기 맛 w와 영양제 p가 존재하며

항상 모든 당근은 초기맛 w 보다 영양제 p의 크기가 더 크며

 

토끼는 하루에 최대 1개의 당근을 먹을 수 있으며 T일 동안 토끼가 먹을 수 있는 당근의 맛의 최대 합을 구하는 문제이다.

 

문제를 풀기 위해서 일단 무작정 수를 나열해서 값을 어떻게 구해야하는지 찾아보았다.

 

그러다보니 규칙이 존재했으며 왜 이 규칙이 성립하는지 알게되었다.

 

 

당근의 영양제의 크기는 초기 맛보다 항상 크다 즉 T일이 존재하고 최대 당근의 맛을 구하기 위해선 당근을 항상 키우는 것이 유리하다.

만약 중간에 먹을 경우에 다시 초기 맛에서부터 T-먹은 날 -1 * w 값으로 구할 수 있지만 최대 맛이 아니다.

 

따라서 영양제의 크기를 기준으로 정렬을 한 후 그 T-1-먹은날 을 계속 누적하면서 더하면 답이 도출된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int N, M;
vector<pii> v;

bool compare(pii a, pii b) {
    return a.second > b.second;
    if(a.second == b.second) return a.first > b.first;
}

void solve() {
    sort(v.begin(), v.end(), compare);

    // for(auto it : v) {
    //     cout << it.first << " " << it.second;
    //     cout << endl;
    // }
    int cnt = 0;
    ll result = 0;
    for(auto it : v) {
        ll first_taste = it.first;
        ll supple = it.second;

        ll tmp = first_taste + (supple * (M-1-cnt));
        result += tmp;
        cnt++;
    }

    cout << result;
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

 

회고록

처음엔 무조건 dp인줄 알았다 중간에 먹는것이 이득일 수 있지 않을까 생각을 했는데 값을 나열하고 왜 이값이 나오는지 하나씩 뜯어보니

문제 조건에 의해서 그리디로 풀 수 있는것이 성립하였다.. 뭔가 독특한 문제인것 같다.