도시락 데우기

• 1. Problem
• 2. My Approach
• 3. Implementation
• 4. Textbook Approach
• 5. Implementation
• 6. Analysis
• 7. Feedback

1. Problem

2. My Approach

• 탐욕법(Greedy-Argorithm)을 적용할 수 있는 기본적인 문제라고 소개되어 있다.
• 문제를 잘못 이해해서 애먹었던 문제다. 전자레인지는 1개고 먹는 사람은 도시락 수만큼 있다는 걸 명심하자.
• 가장 최소 시간에 음식을 해 먹기 위해서 몇 가지 예제를 통해 먹는 시간이 가장 오래 걸리는 음식부터 조리를 해야 됨을 알 수 있다.
• 조리가 완료되면 바로 먹기 시작한다.
• 조리를 시작해서 해당 음식을 다먹은 시각이 가장 나중인 값을 결과로 출력한다

  시간이 아니라 시각이라는 것을 명심하자. 즉 이전에 다른 음식들을 조리한 시간의 영향도 받는다.

3. Implementation

bool cmp(pair<int,int> a, pair<int,int>b){
    return a.second > b.second;
}
...
int main(){
  ...
  for(int i=0;i<N;i++)
            lunch.push_back(make_pair(cook[i], eat[i]));

  sort(lunch.begin(), lunch.end(), cmp);
  int start_eat = 0;
  int ret=0;
  for(int i=0;i<N;i++){
      start_eat += lunch[i].first;
      ret = max(start_eat+lunch[i].second, ret);
  }
  ...
}

• vector< pair<int, int> > 타입의 변수 lunch를 내림차순으로 정렬하기 위해 따로 비교함수 cmp를 선언해주었다.

4. Textbook Approach

• 기본적인 접근 방법은 같으나 도시락을 먹는 데 걸리는 시간의 역순으로 정렬하였다.

  이 것이 의미하는 것도 사실상 본인의 알고리즘과 같다. 내림차순으로 정렬하려면 기존의 sort에서 따로 비교함수를 구현해줘야 하는데, 책에선 먹는 시간을 음수로 나타내 기본 정렬하므로 사실상 먹는 시간이 오래걸리는 것부터 내림차순을 의도한 것과 같다.

5. Implementation

int heat() {
    vector<pair <int, int> > order;
    for(int i = 0; i < num; i++)
        order.push_back(-e[i], i);
    sort(order.begin(), order.end());
    int answer = 0, beginEat = 0;
    for(int i = 0; i < num; i++){
        int box = order[i].second;
        beginEat += m[box];
        answer = max(answer, beginEat + e[box]);
    }
    return answer;
}

6. Analysis

• 두 코드 모두 전체 시간 복잡도는 정렬에 걸리는 O(nlgn)이 지배하게 된다.

7. Feedback

• 주어진 배열을 정렬하는 sort 사용에 대해 익숙해지자.

#include <algorithm>

using namespace std;

• void sort (RandomAccessIterator first, RandomAccessIterator last);
• void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);