algospot LUNCHBOX Microwaving Lunch Boxes

문제

https://algospot.com/judge/problem/read/LUNCHBOX

걸린 시간

01 : 10 : 38

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n, tmp;
        cin >> n;
        vector<int> m, e; // microwave, eating
        for(int i = 0; i < n; i++){
            cin >> tmp;
            m.push_back(tmp);
        }
        for(int i = 0; i < n; i++){
            cin >> tmp;
            e.push_back(tmp);
        }
        // make pair
        vector<pair<int, int>> p;
        for(int i = 0; i < n; i++)
            p.push_back(make_pair(e[i], m[i]));
        // ascending sort by eating
        sort(p.begin(), p.end(), greater<pair<int, int>>());
        // solve
        int start = 0, end;
        int maxv = 0; // max value
        for(int i = 0; i < n; i++){
            end = 0;
            start += p[i].second; // m
            end = start + p[i].first; // e
            if(maxv < end)
                maxv = end;
        }
        if(end <= maxv)
            cout << maxv << "\n";
        else
            cout << end << "\n";
    }
    return 0;
}

1. 문제를 손으로 직접 풀어보고 직관을 얻는 과정
2. vector pair 값 내림차순 정렬 algorthim 사용법 구글링
3. 오답 결과를 받고 더 다양한 예제들을 시도해본 후 올바른 그리디 알고리즘을 구현

들인 시간은 1 >= 3 > 2 순서가 되겠다.