알고리즘

algospot :: LUNCHBOX 도시락 데우기

happilee12 2017. 10. 17. 21:44
반응형

문제 : 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; }




반응형