탐욕법 - 도시락 데우기

 

탐욕법 - 도시락 데우기

 

 

문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/LUNCHBOX

 

 

 

 

 

 

탐욕법

여러 개의 조각으로 쪼개는 방법. 이는 완전탐색, 동적 계획법이랑 같음.

각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 지금 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려하지 않는다.

 

가장 중요한 건 정당성 증명 (최적 부분 구조)

만약 제일 안 좋은 것이 있다면 그것을 최적해로 가정하자.

그리고 더 좋은 것을 찾으면 그것이 최적해라고 한다.

이렇게 결국 제일 좋은 것을 찾아가 최적해를 찾는다.

귀류법같은 느낌이 난다.

 

 

 

 

풀이생각

i번째 도시락 데우기 + 먹기. 어느번째 도시락이 오래 걸릴까 체크

 

i번째 시간 = 데우기시간 + 먹기시작한시간 + 먹기시간

결국엔 다 먹는 시간이 큰 것을 고르면 될 것임.

시간들 중에서 가장 큰 것을 출력. => 최대값 구하기

 

먹는시간(e)가 큰 것이 앞으로 가야 최소시간이 됨. 먹는 시간은 중복이 되기 때문에.

=> e배열을 내림차순으로.

 

내림차순 

1. sort(p, p+n, 콜백함수);

2. sort(p, p+n, greater<pair<int,int>>());

 

 

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int n, m[10000], e[10000];
pair<int, int> p[10000];
 
bool compare(pair<int,int> a, pair<int, int> b) {
    return a.first > b.first;
}
 
int func() {
    int start_eat = 0;
    int res = 0;
    
    for (int i = 0; i < n; ++i) {
        p[i] = make_pair(e[i], i);
    }
 
    sort(p, p+n, compare);
    
    for (int i = 0; i < n; ++i) {
        start_eat += m[p[i].second];
        res = max(res, start_eat + e[p[i].second]);
    }
 
    return res;
}
 
int main() {
    cin.sync_with_stdio(false);
 
    int T; // T <= 300
 
    cin >> T;
    
    for (int i = 0; i < T; ++i) {
        cin >> n;
        memset(m, 0, sizeof(m));
        memset(e, 0, sizeof(e));
        for (int j = 0; j < n; j++) {
            cin >> m[j];
        }
        for (int j = 0; j < n; j++) {
            cin >> e[j];
        }
 
        cout << func() << "\n";
    }
}