Boj 1931 & 4796c++ 회의실 배정 + 캠핑(그리디 공부 시작)

동전0, 설탕 배달을 시작으로 그리디 문제들을 조금씩 건드려보기로 했다.

이번 문제들은 그리디 알고리즘(탐욕 알고리즘)의 기초적인 문제이므로 이번에 한번 풀이 했으니 앞으로도 새로운 방법으로 반복풀이를 해볼 예정이다.

 

*탐욕알고리즘이란?

탐욕 알고리즘 또는 그리디 알고리즘(greedy algorithm)은 최적의 해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

 

마지막 문장, 지역적으로 최적이면서 전역적으로 최적인 케이스에 대해서 이해하려면 캠핑 문제를 풀어보는 것이 좋다. 해당 문제 또한 그리디 알고리즘의 기초문제로, V일의 휴가가 있으며, 캠핑장은 연속한 P일중 L일만 사용이 가능할 때 캠핑장을 이용할 수 있는 최대 일수를 구하는 문제이다. 이 문제는 V일의 휴가를 우선 P일로 나눈 후 , 그 몫에 L일을 곱한다. 그 후, 남은 휴가일에 대하여 최대한 휴일을 갈 수 있도록 계산하는 것이였다. 남은 일수에 대한 연산은 삼항연산자로 처리 할 수 있다. 제출 코드는 다음과 같다.

#include<iostream>
using namespace std;

int main(){
int l, p, v, cnt=0, ans;
    
    while(1){
     cnt++;
     cin>>l>>p>>v;
     if(l==0 && p==0 && v==0){
      break;
}
        ans=(v/p)*l+(((v%p)>l) ? l:(v%p));
    printf("Case %d: ", cnt);
        cout<<ans<<"\n";
}

}

이 문제는 탐욕 알고리즘이 사용가능한 어떤 케이스에 대해서, 지역적으로 최적인 해답은 전역적으로도 최적이라는 것을 이용한 문제이다. 이처럼 탐욕알고리즘은 눈 앞의 이익만을 추구하는 특성을 이용하여 최적해를 구하는 방식이다. 이점을 유념하고  Boj 1931을 풀이해보겠다.

 

문제 상황은 다음과 같다.

 

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

이때, 출력 예제와 힌트를 살펴보면 모두 끝나는 시간 기준으로 선택되었다는 것을 알 수 있다. 즉, 이 문제에서 최적해를 구하는 방법은 가장 먼저 끝나는 회의를 겹치지 않게 순서대로 뽑는 것이다.

 

이를 구현하기 위해서는 회의가 끝나는 시간을 기준으로 정렬하되, 끝나는 시간이 같은 경우, 더 일찍 시작하는 회의가 먼저 오도록 해야 한다. 이는 vector<pair<int, int>> v 가 정렬되는 방식을 활용하여 해결할 수 있다. 벡터 v를 정렬함수를 사용하여 정렬하면 우선은 v.first를 기준으로 정렬되며, 동률인 경우에 v.second를 기준으로 또다시 정렬된다. 이를 이용하여 회의가 끝나는 시간을 v.first, 회의가 시작하는 시간을 v.second에 저장하여 오름차순 정렬하면 원하는 값을 얻을 수 있다. 제출 코드는 다음과 같다.

#include<iostream>
#include<algorithm>
#include<vector>


using namespace std;

int main(){

   ios_base :: sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);

  int N, cnt=0, start;


  cin>>N;
  vector<pair<int, int>> v(N);

  for(int i=0; i<N; i++){
    cin>>v[i].second>>v[i].first;


  }

  sort(v.begin(), v.end());

  start=v[0].first;
  cnt++;

  for(int i=1; i<N; i++){
    if(v[i].second < start)
        continue;
    start=v[i].first;
    cnt++;
  }

  cout<<cnt;


}

 

회의 시간이 겹치지 않게 하기 위해서 시작시간이 현재 최적인 회의종료시간 이후일 경우에만 반복문내의 코드를 실행하도록 하였다. 이렇게 회의가 시작될 때마다 cnt값을 더해주면 정답을 구할 수 있다. 이때, sort함수는 배열의 처음과 끝을 기준으로 정렬하기 때문에, 입력되는 값 +1 만큼의 공간만을 동적할당하여 정렬 중간에 의도치 않은 값이 삽입되는 것을 방지해야 한다.