[백준 C++] 1931, 4307번 회의실배정, 개미 - 그리디 알고리즘

회의실배정

개미

이 링크에는 그리디 알고리즘(탐욕법)을 활용해 풀 수 있는 문제들이 몇가지 있다. '동전 0' 문제는 전에 풀어서 이번에는 풀지 않았고, 'ATM'과 '로프'는 상대적으로 난이도가 낮았으므로 따로 포스팅을 하지 않고, '회의실배정'과 '개미' 문제를 풀면서 그리디 알고리즘을 어떻게 적용시킬 것인지 고민해봤다.

그리디 알고리즘

그리디 알고리즘은 문제를 해결하기 위해 문제를 여러 개의 조각으로 나누고, 각 조각의 답을 바탕으로 답을 찾는다는 점에서 동적계획법과 비슷한 점이 있다. 하지만 동적계획법은 문제 해결을 위해 (거의) 모든 선택지를 고려해보고 그 중 답에 해당되는 것을 고르는 것인 반면, 그리디 알고리즘은 조각에 해당하는 작은 문제를 풀 때마다 최선의 방법만을 선택하기 때문에 최선이 아닌 선택지는 고려하지 않는다.

그렇기 때문에 그리디 알고리즘은 동적계획법에 비해 메모리를 절약하고, 시간을 단축할 수 있는 방법이라고 할 수 있다. 너무 좋아보이는 것이기에 아쉽게도 그리디 알고리즘을 활용해 문제를 풀 수 있는 경우는 제한되어 있다. 

1. 부분 문제에서 최선의 선택을 할 수 있는 방법이 있어야 한다.(최선의 선택을 할 수 없는 문제도 있고, 최선의 선택을 하는 방법이 여러 개 있어 그 중 하나를 선택해야 하는 경우도 있다)
2. 계속해서 최선의 선택을 했다면 최종 결과 또한 최선이어야 한다.

특히 모든 부분 문제에서 최선의 선택을 하는 것(= 탐욕적으로 선택하는 것)은 직관적이지 않기 때문에 자신이 생각해낸 방법으로 문제를 해결할 수 있는지 증명해야 한다.

회의실배정

하나의 회의실을 두고 여러 팀이 사용하려고 할 때 가장 많은 팀이 회의실을 사용하게 하려면 몇 팀까지 사용할 수 있는지 구하는 문제다. 각 팀이 회의실을 사용하고자 하는 시작시간과 사용을 마치는 종료시간이 주어진다.

이 문제를 해결하기 위해 다음과 같은 방법을 떠올렸다고 하자.

 

남아있는 팀들 중에서 종료시간이 가장 빠른 것을 고른다. 이 때 이미 회의실을 사용하고 있는 팀과 시간이 겹치는 팀이 있다면, 이 팀의 신청은 애초에 고려하지 않는다.

그렇다면 그리디 알고리즘을 사용하기 위해서는 '종료 시간이 가장 빠른 회의를 포함하는 최적해가 반드시 존재한다'는 것을 보여야 한다. 귀류법으로 증명할 수 있다.(종만북과는 조금 다름) '종료시간이 가장 빠르지 않은 회의를 포함하는 최적해가 반드시 존재한다'라는 것이 틀렸음을 보이면 된다. 종료시간이 가장 빠른 회의를 a라 하고, 그렇지 않은 것 하나를 b라 하자. b를 포함한 최적해가 존재해야 한다. a의 종료시간이 가장 빠르므로 b의 종료시간은 자연스레 a의 종료시간보다 늦다. 만약 a의 종료시간과 b의 종료시간 사이에 또 다른 최적해가 겹친다면 그 최적해는 이 문제를 해결하는데 아예 사용하지 않는다. 그러므로 답을 도출해낼 수 없고, '종료 시간이 가장 빠르지 않은 것을 포함하는 최적해가 반드시 존재한다'는 틀린 명제가 된다.

(sort 함수를 쓸 때 compare 함수를 직접 만들어 쓴 적이 단 한번도 없어서 한번 만들어봤다. 추후 정리할 예정이다.)

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define FOR(i, N) for(int i = 0; i < N; i++)
struct st { int s, e; };
vector<st> v;
bool cmp(st &a, st &b) {
  if (a.e == b.e) return a.s < b.s;
  else return a.e < b.e;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  int N, a, b;
  cin >> N;
  v.reserve(N);
  FOR(i, N) {
    cin >> a >> b;
    v.push_back(st{a, b});
  }
  sort(v.begin(), v.end(), cmp);
  stack<st> st;
  FOR(i, N) {
    if (st.empty()) st.push(v[i]);
    else if (st.top().e <= v[i].s) st.push(v[i]);
  }
  cout << st.size() << '\n';
}

개미

길이가 l인 막대 위에 개미가 n 마리 있다. 개미들은 각자 왼쪽 혹은 오른쪽으로 움직이는데 막대의 양 끝에 도착하면 떨어진다. 개미들은 서로 마주치면 방향을 바꾼다. 개미가 가는 방향을 임의로 지정할 수 있을 때 모든 개미가 떨어지는데까지 걸린 시간이 가장 짧은 것과 가장 긴 것을 구하는 것이다.

이 문제를 해결하기 위해 다음과 같은 방법을 떠올렸다고 하자. 

길이가 10인 막대 위에 개미 3마리가 각각 2, 6, 7에 위치하고 있을 때, 왼쪽으로 갔을 때의 거리, 오른쪽으로 갔을 때의 거리 중 작은 것을 a, 큰 것을 b로 표현한다면 (2, 8), (4, 6), (3, 7)로 표현할 수 있다. a만큼 가서 떨어지면 충돌없이 가까운 모서리로 가서 떨어지므로 시간이 가장 적게 걸리고(2는 왼쪽, 6, 7은 오른쪽으로), b만큼 가서 떨어지면 충돌하며 먼 모서리로 가서 떨어지므로 시간이 가장 오래 걸린다(2는 오른쪽, 6, 7은 왼쪽으로).

그렇다면 각각의 개미들이 가까운 모서리로 향하면 가장 빨리 떨어지기 위한 최적해가 되고, 각각의 개미들이 먼 모서리로 향하면 가장 느리게 떨어지기 위한 최적해가 된다는 것을 보여야 한다. 위와 마찬가지로 귀류법을 통해 증명한다. 

모든 개미들이 가까운 모서리로 향하는데 한 개미가 먼 모서리로 향해 간다고 하자. 모든 개미들은 빨리 떨어지기 위해 정해진 거리(a)만 가면 되는데 개미 하나가 반대 방향으로 오면서 개미들의 방향을 바꿔놓는다. 이 때 시간의 지연이 생기므로 가장 빨리 떨어지는 최적해가 되지 못한다.

이번에는 모든 개미들이 먼 모서리로 향하는데 한 개미가 가까운 모서리로 향해 간다고 하자. 이 개미가 하필 가장 늦게 떨어지는 개미(b가 가장 큰 개미)라고 한다면 최적해가 달라진다. 모든 개미들은 늦게 떨어지기 위해 정해진 거리(b)만큼을 가줘야 하는데 가장 늦게 떨어지는 개미가 개미가 (l - b)만큼만 가서 떨어지기 때문이다. 예를 들어, 위 예제에서 2에 위치한 개미가 원래는 오른쪽으로 가서 가장 늦게 떨어져야 하는데 왼쪽으로 간다면 가장 늦게 떨어지는데 걸리는 시간은 7이 되고, 이는 최적해가 아니게 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  int TC, l, n, a, b;
  cin >> TC;
  while (TC--) {
    int fast = 0, late = 0;
    cin >> l >> n;
    while (n--) {
      cin >> a;
      b = l - a;
      if (a > b) swap(a, b);
      fast = max(fast, a);
      late = max(late, b);
    }
    cout << fast << " " << late << '\n';
  }
}