[ALGOSPOT] 알고스팟 LUNCHBOX Microwaving Lunch Boxes(C++, Python)

www.algospot.com

[ALGOSPOT] 알고스팟 LUNCHBOX Microwaving Lunch Boxes

(C++, Python)

(글쓴날 : 2020.04.29)

 

---

* ALGOSPOT, 알고스팟 LUNCHBOX 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 LUNCHBOX Microwaving Lunch Boxes

---

1) 문제

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

algospot.com :: LUNCHBOX

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

먹는 시간이 E만큼 걸리고 전자레인지에 데우는 데 M만큼 걸리는 N개의 도시락이 주어질 때 모든 도시락을 먹는 최소 시간을 구하는 문제입니다.

 

저의 경우, 그리디를 적용하였으며, C++과 Python을 사용했습니다.

정렬을 어떻게 하는지가 관건인 문제였는데, 곰곰이 생각하다 보니 도시락을 전자레인지에 데우는 시간은 절대적이라 줄일 수가 없고, 도시락을 먹는데 걸리는 시간은 순서에 영향을 받는다는 사실을 발견했습니다.

그에 따라, 각 도시락의 데우는데 걸리는 시간과, 먹는데 걸리는 시간을 하나의 데이터(C++ : pair, Python :  tuple)로 합쳐, 먹는데 걸리는 시간을 기준으로 내림차순 정렬하였고, 마지막 도시락을 데우고 나서도 남아있는 먹는데 걸리는 시간을 구하여 총 도시락을 데우는데 걸리는 시간과 더해 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>
 
using namespace std;
 
struct cmp
{
    bool operator()(pair<int, int> oldValue, pair<int, int> newValue)
    {
        return oldValue.second > newValue.second;
    }
};
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int T = 0;
    cin >> T;
 
    int N = 0;
    vector<int> microwaveTime, eatingTime;
    vector<pair<int, int>> total;
    int eachTime = 0;
 
    while (T--)
    {
        cin >> N;
        int time = 0;
        int remainingEatingTime = 0;
 
        microwaveTime.clear();
        eatingTime.clear();
        total.clear();
 
        for (int i = 0; i < N; i++)
        {
            cin >> eachTime;
            microwaveTime.push_back(eachTime);
        }
        for (int i = 0; i < N; i++)
        {
            cin >> eachTime;
            eatingTime.push_back(eachTime);
        }
        for (int i = 0; i < N; i++)
        {
            time += microwaveTime[i];
            total.push_back({microwaveTime[i], eatingTime[i]});
        }
 
        sort(total.begin(), total.end(), cmp());
 
        for (int i = 0; i < N; i++)
        {
            remainingEatingTime -= total[i].first;
            remainingEatingTime = max(total[i].second, remainingEatingTime);
        }
 
        time += remainingEatingTime;
 
        cout << time << "\n";
    }
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
T = int(input())
 
for _ in range(T):
    N = int(input())
    time = 0
    remainingEatingTime = 0
 
    microwaveTime = list(map(int, input().split()))
    eatingTime = list(map(int, input().split()))
    total = []
 
    for i in range(N):
        time += microwaveTime[i]
        total.append((microwaveTime[i], eatingTime[i]))
 
    total = sorted(total, key=lambda x: (-x[1]))
    
    for i in range(0, N):
        remainingEatingTime -= total[i][0]
        remainingEatingTime = max(total[i][1], remainingEatingTime)
        
    time += remainingEatingTime
 
    print(time)

---