algospot :: LUNCHBOX 도시락 데우기

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

알고리즘 문제 해결 전략 p.397

책을 참고하지 않고 코드를 작성함

[알고리즘 SPEP. 1]

최대한 효율적으로 도시락을 데워 먹으려면, 어차피 전자레인지는 계속 돌아가야 한다.

전자레인지에 돌리는 시간의 합(A) + 먹는데 쓰는 것 중에 저 시간을 넘어가는 시간(B)

을 최소화 해야 하는데, A는 어차피 고정값이고 B를 어떻게 최소화 할 지를 생각해야한다.

어차피 전자레인지를 다 돌린 후에야 도시락을 먹을 수 있으므로, 도시락 데우는 시간은 고려하지 않고, 먹는 시간이 짧은 순으로 도시락들을 정렬한다.

그 다음에 그 순서의 역순으로 전자레인지를 돌리도록 하면 최적의 해를 구할 수 있다. 즉 "먹는 시간이 짧은 순으로 선택"만 그리디로 구현하면 된다.

다음 예시를 위의 알고리즘대로 풀어보자. 

도시락의 수 5

먹는데 걸리는 시간 1 1 1 1 20

데우는데 걸리는 시간 3 2 4 5 10

이미 먹는데 걸리는 시간대로 정렬해놓은 상태이다.

여기서 데우는데 걸리는 시간을 일단 다 더하고, (= 24) 그 다음에 먹는데 걸리는 시간이 작은 순서대로 다음 그림처럼 붙여 본다.

다섯개의 도시락은 순서대로 A, B, C, D, E로 표현했고, 데우는 시간은 회색 데우는 시간은 주황색으로 표현했다.

[최종코드]

#include <iostream> #include <algorithm> #include <vector> #define FOR(var, ed) for(int var = 0; var<ed; var++) using namespace std; //input int tc, n; bool compare(const pair<int, int>&i, const pair<int, int>&j) { return i.second < j.second; } int greedy(const vector<pair<int,int>> &a, int heatEnds){ // 총 데우는 시간 + 0번쨰 도시락 먹는시간이 예상 답변 int ret = heatEnds + a[0].second; //index에는 i번째 이전의 도시락까지 데우는 시간이 저장되어 있음 int index = heatEnds - a[0].first; for(int i = 1; i < n ; i++){ // 만약에 i번째도시락을 데운 후 먹는 시간이 지금 예상답변보다 길어진다면 // i번째 도시락을 데운 후 먹는 시간이 새로운 답변이 됨 ret = max(ret, index+a[i].second); // i번째 도시락 데우는 시간을 뺌 index -= a[i].first; } return ret; } int main(){ // freopen("input.txt", "r", stdin); cin >> tc; while(tc--){ cin >> n; //pair<int, int> n개짜리 벡터를 선언 vector<pair<int, int>> food(n); //도시락 정보를 입력받으면서 총 도시락 데우는 시간을 계산 -> ret에 저장 int ret = 0; FOR(i, n) { cin >> food[i].first; ret += food[i].first; } FOR(i, n) cin >> food[i].second; // 도시락 먹는 시간을 기준으로 도시락 정보를 정렬 sort(food.begin(),food.end(),compare); cout << greedy(food, ret) << endl; } }

[새로 알게 된 것들]

-vector<pair<int, int>> 를 특정 인덱스로 정렬 

bool compare(const pair<int, int>&i, const pair<int, int>&j) { return i.second < j.second; }